This notebook is written with reticulate, a package that allows inter-operation between R and Python.


1 Motivation

Why do we need to explain a machine learning model? The benefit of an explanable model against a black-box model is for the model to be trusted. Trust can be important in many real applications where the successful deployment of a machine learning model requires the trust from end users. Sometimes trust plays a even bigger role than model accuracy.

Other than trust, model explainability (or interpretability, interchangeably used hereafter) may also guide us in the correct direction to further improve the model.1

In general, linear model is more interpretable than non-linear model. But the former also suffers from lower accuracy. More advanced and hence complicated model usually has worse interpretability.

One should not confuse model explainability with the actual causality. Being able to explain a model doesn’t mean that we can identify any ground-truth causal relation behind the model. Model explainability is for and only for the model, but not for the facts we’d like to model. Nevertheless, understand how we can reason the model definitely will help us better model the actual pattern behind the scence.

In this notebook we will walk through 3 popular approaches of model prediction explanation, each of them comes with a dedicated Python package:

  1. shap
  2. lime
  3. interpret

2 Explanation Models

An explanation model \(g(x)\) is an interpretable approximation of the original model \(f(x)\). Its sole purpose is to give extra explainability the original model fails to provide, due to its own complexity.

The general idea is to use a simplified input \(x\prime\) such that \(x = h_x(x\prime)\), where \(h_x(\cdot)\) is a mapping function for any given raw input \(x\). Then the interpretable approximation can be written as:

\[ g(x\prime) \approx f(h_x(x\prime)). \]

The additive feature attribution methods specify the explanation model of the following form:

\[ g(x\prime) = \phi_0 + \sum_{i = 1}^m \phi_i x_i\prime, \]

where \(m\) is total number of simplified features, \(x\prime \in \{0, 1\}\) simply an indicator.2 Apparently, the choice of an additive model is for (linear) intrepretability. The simplified features are an interpretable representation of the original model features.

3 LIME

One very popular such above additive model is LIME (Ribeiro, Singh, and Guestrin (2016)). LIME stands for Local Interpretable Model-Agnostic Explanations. As its full name suggests, LIME can be applied to any machine learning model. LIME achieves prediction-level interpretability by approxmiating the original model with an explanation model locally around that prediction.

TODO: Add theory briefing here.

3.1 On Text Classifiers

For text classification problem, the most straightforward interpretable representation of the model features will be a binary indicator vector of bag of words. So the explanation model will try to reason which word or token is driving the prediction in what direction. And this is true no matter the form of the original model feature. May it be a word count matrix, a term frequency-inverse document frequency (TF-IDF) matrix, or numerical embeddings.

In the following we will use Large Movie Review Dataset to do a binary sentiment classification exercise. We will use machine learning libraries such as scikit-learn and tensorflow to quickly build models and use lime to experiment explanation modeling.

import os
import logging
logging.getLogger("tensorflow").setLevel(logging.ERROR)
import warnings
warnings.simplefilter(action="ignore", category=UserWarning)
warnings.simplefilter(action="ignore", category=FutureWarning)

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

import tensorflow as tf
print(tf.__version__)
2.0.0
if tf.test.is_gpu_available():
  print(tf.test.gpu_device_name())
/device:GPU:0
import sklearn
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.ensemble import RandomForestClassifier
from sklearn.pipeline import make_pipeline
from sklearn.metrics import classification_report, roc_auc_score
from sklearn.model_selection import train_test_split
import joblib

print(sklearn.__version__)
0.22
# Create model dir to cache all models trained in the notebook.
model_dir = "models"
if not os.path.exists(model_dir):
    os.makedirs(model_dir)

# Directory to cache dataset.
home = os.path.expanduser("~")
cache_dir = os.path.join(home, ".keras")

First, we prepare the movie review dataset.3

import tensorflow_datasets as tfds

# Load the data as tf.data.Dataset.
imdb = tfds.load(name="imdb_reviews", as_supervised=True,
                 data_dir=os.path.join(home, "tensorflow_datasets"))

The dataset is a perfectly balanced dataset with 50,000 examples, half for positive and half for negative sentiment.

# Extract all texts as list since we want to use libraries other than tensorflow as well.
# And since this is a small dataset, we don't care about memory usage.
# We skip the use of a dataset iterator.
imdb_reviews_train = []
imdb_reviews_test = []
imdb_y_train = []
imdb_y_test = []
for x, y in imdb["train"].batch(128):
  imdb_reviews_train.extend(x.numpy())
  imdb_y_train.extend(y.numpy())
for x, y in imdb["test"].batch(128):
  imdb_reviews_test.extend(x.numpy())
  imdb_y_test.extend(y.numpy())

# TF works on bytes, but some other packages may only work on decoded string.
imdb_reviews_train = [b.decode("utf8") for b in imdb_reviews_train]
imdb_reviews_test = [b.decode("utf8") for b in imdb_reviews_test]
imdb_y_train = np.array(imdb_y_train)
imdb_y_test = np.array(imdb_y_test)

# Take one review.
print(imdb_reviews_train[87])
Any movie that portrays the hard-working responsible husband as the person who has to change because of bored, cheating wife is an obvious result of 8 years of the Clinton era.<br /><br />It's little wonder that this movie was written by a woman.
print(imdb_y_train[87])  # Label. 0 as negative and 1 as positive.
0

We use the data prepared by tensorflow-datasets here just to save some time. For those who want to process the data in its very original format (where one review is in one .txt file), the files can be downloaded by this piece of code:

imdb_remote_path = "https://ai.stanford.edu/~amaas/data/sentiment/aclImdb_v1.tar.gz"
imdb_fname = os.path.basename(imdb_remote_path)
imdb_local_path = os.path.join(cache_dir, "datasets", imdb_fname)

if not os.path.exists(imdb_local_path):
  _ = tf.keras.utils.get_file(fname=imdb_fname, origin=imdb_remote_path,
                              extract=True, cache_dir=cache_dir)

3.1.1 Explain Random Forest

Let’s build a random forest with TF-IDF as our feature space. We will use the popular scikit-learn library for implementation.4

# We drop words that are too frequent or too rare in the training dataset.
imdb_vectorizer = TfidfVectorizer(lowercase=True, min_df=10, max_df=.9)
imdb_X_train = imdb_vectorizer.fit_transform(imdb_reviews_train)
imdb_X_test = imdb_vectorizer.transform(imdb_reviews_test)
print(len(imdb_vectorizer.vocabulary_))  # Without OOV token.
18518
imdb_rf_model_file = os.path.join(model_dir, "text_rf.joblib")

# Save/reload the model to save notebook rendering time.
if os.path.exists(imdb_rf_model_file):
  imdb_rf = joblib.load(imdb_rf_model_file)
else:
  imdb_rf = RandomForestClassifier(n_estimators=300, random_state=64, n_jobs=-2)
  _ = imdb_rf.fit(imdb_X_train, imdb_y_train)
  _ = joblib.dump(imdb_rf, imdb_rf_model_file)

imdb_rf_pred = imdb_rf.predict(imdb_X_test)
imdb_rf_yhat = imdb_rf.predict_proba(imdb_X_test)[:,1]

print(classification_report(imdb_y_test, imdb_rf_pred))
              precision    recall  f1-score   support

           0       0.84      0.86      0.85     12500
           1       0.86      0.84      0.85     12500

    accuracy                           0.85     25000
   macro avg       0.85      0.85      0.85     25000
weighted avg       0.85      0.85      0.85     25000
print(roc_auc_score(imdb_y_test, imdb_rf_yhat))
0.9274221727999999

As a baseline without extensive tuning (we didn’t tune anything indeed!), random forest seems to perform fairly well on this dataset.

As part of the algorithm’s design we are able to derive a global view of feature importance. This is based on how much each feature can reduce the impurity during all tree splittings. For example, we can plot the top 20 features:

sorted_vocab = sorted(imdb_vectorizer.vocabulary_.items(), key=lambda kv: kv[1])
sorted_vocab = [w for w, i in sorted_vocab]

imdb_rf_feat_imp = pd.Series(imdb_rf.feature_importances_, index=sorted_vocab).sort_values()
ax = imdb_rf_feat_imp.tail(20).plot(kind="barh")
plt.show()

As one can see, common adjectives describing good or bad things generally have larger impact in the model, which is totally expected. But we also see influential words such as just and minutes which are quite neutral and contain no useful information on their own. They may be jointly important in the model since a tree model allows interaction between variables. But we won’t be able to go deeper beyond the unconditional view we derived as a global feature ranking.

Interpretation of the impurity-based ranking must be very careful. For example, related features will theoretically have similar impact but only one of it will gain higher score (and suppress the other) in the ranking. Which one stands out is totally random due to the way tree splitting is performed during training.

In general it is NOT recommended to use impurity or loss-based feature ranking to interpret a tree ensemble model. Such ranking information is still useful to understand different aspects of the model, and can be used to subset feature to counter over-fitting issue, if any. But it won’t help really explain the model at the prediction-level: Why is my model making such prediction? And this is exactly why we need a explanation model in the first place.

Now move on to model explanation with LIME. We pick up one true positive and one false positive case made by our random forest model to see how the explanation model will explain each case.

from lime.lime_text import LimeTextExplainer

# We need a pipeline since LimeTextExplainer.explain_instance expects raw text input.
imdb_rf_pipe = make_pipeline(imdb_vectorizer, imdb_rf)
imdb_rf_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

imdb_rf_tp_idx = np.where(np.logical_and(imdb_rf_pred == 1, imdb_y_test == 1))[0]
imdb_rf_fp_idx = np.where(np.logical_and(imdb_rf_pred == 1, imdb_y_test == 0))[0]

# We take one true positive and one false positive example to demo explanation.
imdb_rf_tp_exp = imdb_rf_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], imdb_rf_pipe.predict_proba, num_features=6)
imdb_rf_fp_exp = imdb_rf_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], imdb_rf_pipe.predict_proba, num_features=6)
# For ipynb, one can simply call imdb_tp_exp.show_in_notebook(text=True) to embed the html output.

imdb_rf_tp_exp.save_to_file("/tmp/explain_text_rf_tp.html")
imdb_rf_fp_exp.save_to_file("/tmp/explain_text_rf_fp.html")

A True Positive Prediction Explained


Our RF model doesn’t seem to be very confident on this particular positive example indeed. There is no dominant single word can drive the prediction in the correct direction. The contributing words are also mostly neutral on their own. We can confirm that the result of this prediction will be very sensitive and not robust. Admittedly this review does show some mixtures of positive and negative views.

A False Positive Prediction Explained

Now let’s look at a false positive example, where our RF model wrongly labeled as a positive review.


In this example a single positive word great (wrongly) dominate the prediction toward a positive sentiment. And we realize the model didn’t response well to some negative signals, especially for the word bore.

If we examine more cases we may have more clues on how the model mis-behaves, and we can come up with a strategy accordingly to improve it. For now we’ll stop here and try experimenting with other learning algorithms hereafer.

3.1.2 Explain Neural Networks

Now let’s try a shallow neural network model with word embeddings trained from scratch. We use tensorflow.keras API to quickly build and train a neural net. We average word embeddings as the document embeddings for each review, then feed-forward a ReLU layer before the sigmoid activation for cross-entropy optimization.

As an exercise, instead of re-using the vocabulary built by TfidfVectorizer with scikit-learn, we will re-tokenize the text data with keras.preprocessing module. The inherent consistency under the Keras framework will also simplify our latter works on network layering.

from tensorflow.keras.preprocessing.text import Tokenizer
from tensorflow.keras.preprocessing.sequence import pad_sequences

# Build vocabulary. We use similar size as in our previous TfidfVectorizer.
# Since we will use zero padding, 0 cannot be used as OOV index.
# Keras tokenizer by default reserves 0 already. OOV token, if used, will be indexed at 1.
# Note that len(tokenizer.index_word) will be all vocabulary instead of `num_words`.
vocab_size = 20001  # +1 for 0 index used for padding.
oov_token = "<unk>"
tokenizer = Tokenizer(lower=True, oov_token=oov_token, num_words=vocab_size)
tokenizer.fit_on_texts(imdb_reviews_train)

# Encode text with padding to ensure fixed-length input.
seq_train = tokenizer.texts_to_sequences(imdb_reviews_train)
seq_train_padded = pad_sequences(seq_train, padding="post")
maxlen = seq_train_padded.shape[1]
seq_test = tokenizer.texts_to_sequences(imdb_reviews_test)
seq_test_padded = pad_sequences(seq_test, padding="post", maxlen=maxlen)

assert tokenizer.index_word[1] == oov_token
assert seq_train_padded.max() == vocab_size - 1

# Wrap Keras Sequential model with scikit-learn API.
# This is because LimeTextExplainer seems buggy with a native Keras model.
nn_model_file = os.path.join(model_dir, "text_clf_nn.h5")

def nn_model_fn():
  embedding_size = 64
  model = tf.keras.Sequential([
    tf.keras.layers.Embedding(
      vocab_size, embedding_size, input_length=maxlen,
      mask_zero=True, name="word_embedding"),
    tf.keras.layers.GlobalAveragePooling1D(name="doc_embedding"),
    tf.keras.layers.Dense(embedding_size / 2, activation="relu", name="relu"),
    tf.keras.layers.Dense(1, activation="sigmoid", name="sigmoid")
  ], name="nn_classifier")
  model.compile(optimizer="adam",
                loss="binary_crossentropy",
                metrics=["accuracy"])
  return model

print(nn_model_fn().summary(line_length=90))
Model: "nn_classifier"
__________________________________________________________________________________________
Layer (type)                            Output Shape                        Param #
==========================================================================================
word_embedding (Embedding)              (None, 2493, 64)                    1280064
__________________________________________________________________________________________
doc_embedding (GlobalAveragePooling1D)  (None, 64)                          0
__________________________________________________________________________________________
relu (Dense)                            (None, 32)                          2080
__________________________________________________________________________________________
sigmoid (Dense)                         (None, 1)                           33
==========================================================================================
Total params: 1,282,177
Trainable params: 1,282,177
Non-trainable params: 0
__________________________________________________________________________________________
None
imdb_nn = tf.keras.wrappers.scikit_learn.KerasClassifier(nn_model_fn)
if os.path.exists(nn_model_file):
  # Restore the model with wrapper.
  imdb_nn.model = tf.keras.models.load_model(nn_model_file)
  imdb_nn.classes_ = np.array([0, 1])
else:
  metrics = imdb_nn.fit(
    x=seq_train_padded, y=imdb_y_train,
    batch_size=256, epochs=10,
    validation_data=(seq_test_padded, imdb_y_test),
    validation_steps=20,
    callbacks=[
      tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
      tf.keras.callbacks.ModelCheckpoint(nn_model_file, monitor="val_loss", save_best_only=True)
    ],
    verbose=2)
Train on 25000 samples, validate on 25000 samples
Epoch 1/10
25000/25000 - 12s - loss: 0.6422 - accuracy: 0.7670 - val_loss: 0.1106 - val_accuracy: 0.8174
Epoch 2/10
25000/25000 - 11s - loss: 0.3945 - accuracy: 0.8676 - val_loss: 0.0707 - val_accuracy: 0.8609
Epoch 3/10
25000/25000 - 11s - loss: 0.2580 - accuracy: 0.9062 - val_loss: 0.0610 - val_accuracy: 0.8801
Epoch 4/10
25000/25000 - 11s - loss: 0.1993 - accuracy: 0.9298 - val_loss: 0.0583 - val_accuracy: 0.8854
Epoch 5/10
25000/25000 - 12s - loss: 0.1620 - accuracy: 0.9439 - val_loss: 0.0579 - val_accuracy: 0.8887
Epoch 6/10
25000/25000 - 11s - loss: 0.1337 - accuracy: 0.9565 - val_loss: 0.0603 - val_accuracy: 0.8861
Epoch 7/10
25000/25000 - 11s - loss: 0.1104 - accuracy: 0.9663 - val_loss: 0.0623 - val_accuracy: 0.8871
imdb_nn_yhat = imdb_nn.predict_proba(seq_test_padded)[:,1]
imdb_nn_pred = (imdb_nn_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_nn_pred))
              precision    recall  f1-score   support

           0       0.87      0.90      0.89     12500
           1       0.90      0.87      0.88     12500

    accuracy                           0.88     25000
   macro avg       0.88      0.88      0.88     25000
weighted avg       0.88      0.88      0.88     25000
print(roc_auc_score(imdb_y_test, imdb_nn_yhat))
0.9511709056

Based on the testing AUC score, our shallow neural network model did outperform a random forest. Let’s see how the explanation model tell us about the behavior of the neural network model.

def nn_predict_fn(text):
  # This is for sklearn wrapper only.
  seq = tokenizer.texts_to_sequences(text)
  seq = pad_sequences(seq, padding="post", maxlen=maxlen)
  return imdb_nn.predict_proba(seq)

imdb_nn_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

# Explain the same examples as in RF.
imdb_nn_tp_exp = imdb_nn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], nn_predict_fn, num_features=6)
imdb_nn_fp_exp = imdb_nn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], nn_predict_fn, num_features=6)

imdb_nn_tp_exp.save_to_file("/tmp/explain_text_nn_tp.html")
imdb_nn_fp_exp.save_to_file("/tmp/explain_text_nn_fp.html")


The above is the LIME explanation of the same positive example previously explained with a RF model. We realize that, though both models eventually give a positive prediction, the neural network model has a very different opinion on how the positive prediction is formulated. Instead of being confused and indecisive, the NN model is actually over-confident about this prediction! Some neutral words have disproportionate contribition to the positive, pointing out the potential direction to improve the model. For example, can a bigram tokenizer be better?

How about the second example (which is a negative review)? Our NN model also makes a mistake on this negative review, by predicting it as a positive one.


What’s different here is the reaction to the negative word bore, which is not seen in RF.

Without a explanation model, it won’t be easy for us to compare two models at this level of details.

3.1.3 Explain Transfer Learning

One step further, let’s use pre-trained word embeddings for the neural nets and build another explanation model. We will use GloVe (Pennington, Socher, and Manning (2014)). We use just the smaller GloVe model since our dataset is quite small.

# Download GloVe pre-trained embeddings.
# The file is about 800MB so may take some time.
glove6b_remote_path = "http://nlp.stanford.edu/data/glove.6B.zip"
glove6b_local_path = os.path.join(cache_dir, "datasets", "glove.6B.50d.txt")
glove6b_fname = os.path.basename(glove6b_remote_path)
if not os.path.exists(glove6b_local_path):
  _ = tf.keras.utils.get_file(fname=glove6b_fname, origin=glove6b_remote_path,
                              extract=True, cache_dir=cache_dir)

glove_all = pd.read_csv(glove6b_local_path, sep=" ", header=None, index_col=0, quoting=3)

In building the GloVe embeddings we need to take special care about out-of-vocabulary token AND padding index since we will be using the Keras API.

# Map vocabulary to pre-trained embeddings.
matched_toks = []
for i, w in tokenizer.index_word.items():
  if i < vocab_size:
    if w in glove_all.index:
      matched_toks.append(w)
    else:
      matched_toks.append(oov_token)

# Note that GloVe pre-trained embeddings does not include its own OOV token.
# We will use a global average embedding to represent OOV token.
print(len([t for t in matched_toks if t == oov_token]))  # How many OOVs?
861
glove_all.loc[oov_token] = glove_all.values.mean(axis=0)
glove = glove_all.loc[matched_toks].values

# Append dummy 0-index vector to support padding.
glove = np.vstack([np.zeros((1, glove.shape[1])), glove])
print(glove.shape)
(20001, 50)

Now let’s build the neural network. Most of the code will be the same as before, only the Embedding layer now we will use a constant matrix for initialization. We make the GloVe embeddings trainable so it will further adapt to our specific dataset.

tr_model_file = os.path.join(model_dir, "text_clf_tr.h5")

def tr_model_fn():
  embedding_size = glove.shape[1]
  model = tf.keras.Sequential([
    tf.keras.layers.Embedding(
      vocab_size, embedding_size, input_length=maxlen,
      embeddings_initializer=tf.keras.initializers.Constant(glove),
      trainable=True, mask_zero=True, name="glove_embedding"),
    tf.keras.layers.GlobalAveragePooling1D(name="doc_embedding"),
    tf.keras.layers.Dense(embedding_size / 2, activation="relu", name="relu"),
    tf.keras.layers.Dense(1, activation="sigmoid", name="sigmoid")
  ], name="tr_classifier")
  model.compile(optimizer="adam",
                loss="binary_crossentropy",
                metrics=["accuracy"])
  return model

print(tr_model_fn().summary(line_length=90))
Model: "tr_classifier"
__________________________________________________________________________________________
Layer (type)                            Output Shape                        Param #
==========================================================================================
glove_embedding (Embedding)             (None, 2493, 50)                    1000050
__________________________________________________________________________________________
doc_embedding (GlobalAveragePooling1D)  (None, 50)                          0
__________________________________________________________________________________________
relu (Dense)                            (None, 25)                          1275
__________________________________________________________________________________________
sigmoid (Dense)                         (None, 1)                           26
==========================================================================================
Total params: 1,001,351
Trainable params: 1,001,351
Non-trainable params: 0
__________________________________________________________________________________________
None
imdb_tr = tf.keras.wrappers.scikit_learn.KerasClassifier(tr_model_fn)
if os.path.exists(tr_model_file):
  # Restore the model with wrapper.
  imdb_tr.model = tf.keras.models.load_model(tr_model_file)
  imdb_tr.classes_ = np.array([0, 1])
else:
  imdb_tr = tf.keras.wrappers.scikit_learn.KerasClassifier(tr_model_fn)
  metrics = imdb_tr.fit(
    x=seq_train_padded, y=imdb_y_train,
    batch_size=256, epochs=20,
    validation_data=(seq_test_padded, imdb_y_test),
    validation_steps=20,
    callbacks=[
      tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
      tf.keras.callbacks.ModelCheckpoint(tr_model_file, monitor="val_loss", save_best_only=True)
    ],
    verbose=2)
Train on 25000 samples, validate on 25000 samples
Epoch 1/20
25000/25000 - 12s - loss: 0.6642 - accuracy: 0.6517 - val_loss: 0.1292 - val_accuracy: 0.7049
Epoch 2/20
25000/25000 - 11s - loss: 0.5632 - accuracy: 0.7552 - val_loss: 0.1046 - val_accuracy: 0.7775
Epoch 3/20
25000/25000 - 11s - loss: 0.4285 - accuracy: 0.8298 - val_loss: 0.0828 - val_accuracy: 0.8293
Epoch 4/20
25000/25000 - 11s - loss: 0.3308 - accuracy: 0.8712 - val_loss: 0.0707 - val_accuracy: 0.8535
Epoch 5/20
25000/25000 - 11s - loss: 0.2744 - accuracy: 0.8930 - val_loss: 0.0653 - val_accuracy: 0.8664
Epoch 6/20
25000/25000 - 11s - loss: 0.2378 - accuracy: 0.9081 - val_loss: 0.0613 - val_accuracy: 0.8770
Epoch 7/20
25000/25000 - 11s - loss: 0.2100 - accuracy: 0.9210 - val_loss: 0.0594 - val_accuracy: 0.8836
Epoch 8/20
25000/25000 - 11s - loss: 0.1879 - accuracy: 0.9316 - val_loss: 0.0588 - val_accuracy: 0.8857
Epoch 9/20
25000/25000 - 12s - loss: 0.1686 - accuracy: 0.9396 - val_loss: 0.0585 - val_accuracy: 0.8865
Epoch 10/20
25000/25000 - 11s - loss: 0.1518 - accuracy: 0.9472 - val_loss: 0.0589 - val_accuracy: 0.8873
Epoch 11/20
25000/25000 - 10s - loss: 0.1372 - accuracy: 0.9533 - val_loss: 0.0610 - val_accuracy: 0.8852
imdb_tr_yhat = imdb_tr.predict_proba(seq_test_padded)[:,1]
imdb_tr_pred = (imdb_tr_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_tr_pred))
              precision    recall  f1-score   support

           0       0.86      0.91      0.88     12500
           1       0.91      0.85      0.88     12500

    accuracy                           0.88     25000
   macro avg       0.88      0.88      0.88     25000
weighted avg       0.88      0.88      0.88     25000
print(roc_auc_score(imdb_y_test, imdb_tr_yhat))
0.9518605536

Our NN model with transfer learning has similar AUC score to the vanilla NN. Let’s use explanation modeling to see if there is any actual difference.

def tr_predict_fn(text):
  # This is for sklearn wrapper only.
  seq = tokenizer.texts_to_sequences(text)
  seq = pad_sequences(seq, padding="post", maxlen=maxlen)
  return imdb_tr.predict_proba(seq)

imdb_tr_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

# Explain the same examples as in RF.
imdb_tr_tp_exp = imdb_tr_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], tr_predict_fn, num_features=6)
imdb_tr_fp_exp = imdb_tr_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], tr_predict_fn, num_features=6)

imdb_tr_tp_exp.save_to_file("/tmp/explain_text_tr_tp.html")
imdb_tr_fp_exp.save_to_file("/tmp/explain_text_tr_fp.html")

For the same positive review, again the model shows over-confidence. Even the donimant words are the same.


For the negative review, interestingly, the transfer learning NN indeed makes a correct prediction of negative label. The word bore becomes the main driving force to lower down the score.


3.1.4 Explain Recurrent Neural Nets

As a final exercise on text classification, let’s experiment the explanation modeling with a recurrent neural network (RNN) RNN is known to be able to capture sequential dependencies better than ngram bag-of-words approach.5

rnn_model_file = os.path.join(model_dir, "text_clf_rnn.h5")

def rnn_model_fn():
  embedding_size = glove.shape[1]
  model = tf.keras.Sequential([
    tf.keras.layers.Embedding(
      vocab_size, embedding_size, input_length=maxlen,
      embeddings_initializer=tf.keras.initializers.Constant(glove),
      trainable=True, mask_zero=True, name="glove_embedding"),
    tf.keras.layers.GRU(64, dropout=.2, name="GRU"),
    tf.keras.layers.Dense(1, activation="sigmoid", name="sigmoid")
  ], name="rnn_classifier")
  model.compile(optimizer="adam",
                loss="binary_crossentropy",
                metrics=["accuracy"])
  return model

print(rnn_model_fn().summary(line_length=90))
Model: "rnn_classifier"
__________________________________________________________________________________________
Layer (type)                            Output Shape                        Param #
==========================================================================================
glove_embedding (Embedding)             (None, 2493, 50)                    1000050
__________________________________________________________________________________________
GRU (GRU)                               (None, 64)                          22272
__________________________________________________________________________________________
sigmoid (Dense)                         (None, 1)                           65
==========================================================================================
Total params: 1,022,387
Trainable params: 1,022,387
Non-trainable params: 0
__________________________________________________________________________________________
None
imdb_rnn = tf.keras.wrappers.scikit_learn.KerasClassifier(rnn_model_fn)
if os.path.exists(rnn_model_file):
  # Restore the model with wrapper.
  imdb_rnn.model = tf.keras.models.load_model(rnn_model_file)
  imdb_rnn.classes_ = np.array([0, 1])
else:
  metrics = imdb_rnn.fit(
    x=seq_train_padded, y=imdb_y_train,
    batch_size=32, epochs=10,
    validation_data=(seq_test_padded, imdb_y_test),
    validation_steps=20,
    callbacks=[
      tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
      tf.keras.callbacks.ModelCheckpoint(rnn_model_file, monitor="val_loss", save_best_only=True)
    ],
    verbose=2)
Train on 25000 samples, validate on 25000 samples
Epoch 1/10
25000/25000 - 47s - loss: 0.4787 - accuracy: 0.7584 - val_loss: 0.0079 - val_accuracy: 0.8750
Epoch 2/10
25000/25000 - 41s - loss: 0.2622 - accuracy: 0.8942 - val_loss: 0.0063 - val_accuracy: 0.8969
Epoch 3/10
25000/25000 - 40s - loss: 0.1931 - accuracy: 0.9249 - val_loss: 0.0065 - val_accuracy: 0.9125
Epoch 4/10
25000/25000 - 41s - loss: 0.1484 - accuracy: 0.9445 - val_loss: 0.0059 - val_accuracy: 0.9031
Epoch 5/10
25000/25000 - 40s - loss: 0.1132 - accuracy: 0.9586 - val_loss: 0.0070 - val_accuracy: 0.8984
Epoch 6/10
25000/25000 - 40s - loss: 0.0867 - accuracy: 0.9692 - val_loss: 0.0072 - val_accuracy: 0.9109
imdb_rnn_yhat = imdb_rnn.predict_proba(seq_test_padded)[:,1]  # Interence of RNN take time.
imdb_rnn_pred = (imdb_rnn_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_rnn_pred))
              precision    recall  f1-score   support

           0       0.89      0.90      0.90     12500
           1       0.90      0.89      0.90     12500

    accuracy                           0.90     25000
   macro avg       0.90      0.90      0.90     25000
weighted avg       0.90      0.90      0.90     25000
print(roc_auc_score(imdb_y_test, imdb_rnn_yhat))
0.9611088543999999

RNN with pre-trained GloVe embeddings seems to work very well, even for such a small dataset. That's see how the explanation can differ, again, for the same two examples:

def rnn_predict_fn(text):
  # This is for sklearn wrapper only.
  seq = tokenizer.texts_to_sequences(text)
  seq = pad_sequences(seq, padding="post", maxlen=maxlen)
  return imdb_rnn.predict_proba(seq)

imdb_rnn_explainer = LimeTextExplainer(class_names=["Negative", "Positive"])

# Explain the same examples as in RF.
imdb_rnn_tp_exp = imdb_rnn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_tp_idx[0]], rnn_predict_fn, num_features=6)
imdb_rnn_fp_exp = imdb_rnn_explainer.explain_instance(
  imdb_reviews_test[imdb_rf_fp_idx[0]], rnn_predict_fn, num_features=6)

imdb_rnn_tp_exp.save_to_file("/tmp/explain_text_rnn_tp.html")
imdb_rnn_fp_exp.save_to_file("/tmp/explain_text_rnn_fp.html")

The same over-confidence for all NN models on this particular positive review.


For the negative review, RNN also correctly predict the label. This may relate to they both using the pre-trained embeddings.


3.1.5 From Explanation to Trust

Throughout the exercise above we only demonstrate with two examples, so nothing really conclusive here as which model is more reasonable in making their decision. But with more investigation there may be more insights on which model can be trusted more than the others.

We summarize the benefit of explanation modeling here. In general it allows us…

  1. To reason the model behavior at a single instance level
  2. To investigate unreasonable behavior such that we can further improve the original model with feature engineering
  3. To differentiate different models with similar testing scores
  4. To build trust on a model, especially for the end user, to better formulate the subsequent action item

3.2 On Tabular Data Classifier

Lots of data can be represented in tabular format. Here we will use UCI Heart Disease dataset for demo. Particularly, we use the Cleveland dataset which is commonly used in machine learning research.6

ucihd_remote_path = "https://archive.ics.uci.edu/ml/machine-learning-databases/heart-disease/processed.cleveland.data"
ucihd_fname = os.path.basename(ucihd_remote_path)
ucihd_local_path = os.path.join(cache_dir, "datasets", ucihd_fname)

if not os.path.exists(ucihd_local_path):
  _ = tf.keras.utils.get_file(fname=ucihd_fname, origin=ucihd_remote_path,
                              extract=False, cache_dir=cache_dir)

The dataset contains both numerical and categorical features (all encoded in numerics already, please refer to the in-line comments for documentation). It is tiny in both number of features and number of examples. But as a demo case it should serve well the purpose.

ucihd_attr = [
  "age",
  "sex",      # 0 = female 1 = male
  "cp",       # chest pain type 1: typical angina 2: atypical angina 3: non-anginal pain 4: asymptomatic
  "trestbps", # resting blood pressure (in mm Hg on admission to the hospital)
  "chol",     # serum cholestoral in mg/dl
  "fbs",      # (fasting blood sugar > 120 mg/dl) (1 = true; 0 = false)
  "restecg",  # resting electrocardiographic results 0: normal 1: having ST-T wave abnormality 2: showing probable or definite left ventricular hypertrophy by Estes' criteria
  "thalach",  # maximum heart rate achieved
  "exang",    # exercise induced angina (1 = yes; 0 = no)
  "oldpeak",  # ST depression induced by exercise relative to rest
  "slope",    # the slope of the peak exercise ST segment
  "ca",       # number of major vessels (0-3) colored by flouroscopy
  "thal",     # 3 = normal; 6 = fixed defect; 7 = reversable defect
  "label"     # diagnosis of heart disease (angiographic disease status) 0: < 50% diameter narrowing 1-4: > 50% diameter narrowing
]
ucihd = pd.read_csv(ucihd_local_path, header=None, names=ucihd_attr, na_values="?")
categorical_attr = ["sex", "cp", "fbs", "restecg", "exang", "thal"]
for col in categorical_attr:
  ucihd[col] = ucihd[col].astype("category")

# Clean label.
ucihd.loc[ucihd["label"] > 1, "label"] = 1

print(ucihd.shape)
(303, 14)
print(ucihd.groupby("label").size())  # Label distribution.
label
0    164
1    139
dtype: int64
print(ucihd.head())
    age  sex   cp  trestbps   chol  fbs restecg  thalach exang  oldpeak  slope   ca thal  label
0  63.0  1.0  1.0     145.0  233.0  1.0     2.0    150.0   0.0      2.3    3.0  0.0  6.0      0
1  67.0  1.0  4.0     160.0  286.0  0.0     2.0    108.0   1.0      1.5    2.0  3.0  3.0      1
2  67.0  1.0  4.0     120.0  229.0  0.0     2.0    129.0   1.0      2.6    2.0  2.0  7.0      1
3  37.0  1.0  3.0     130.0  250.0  0.0     0.0    187.0   0.0      3.5    3.0  0.0  3.0      0
4  41.0  0.0  2.0     130.0  204.0  0.0     2.0    172.0   0.0      1.4    1.0  0.0  3.0      0

3.2.1 Explain Random Forest

Again we try to explain tree ensembels.

# sklearn's implementation of RF doesn't allow missing value.
# For categorical (as string) we can leave one special category for missing,
# but for numerical we need to do some special encoding or imputation.
ucihd_2 = ucihd.copy()
ucihd_2.loc[ucihd_2["ca"].isna(), "ca"] = -1  # Encode missing numerical.

# One-hot encode all categorical features.
ucihd_2 = pd.get_dummies(ucihd_2, columns=categorical_attr, dummy_na=True)
ucihd_y = ucihd_2.pop("label")
ucihd_X_train, ucihd_X_test, ucihd_y_train, ucihd_y_test = train_test_split(
  ucihd_2, ucihd_y.values, test_size=.3, random_state=64)

ucihd_rf = RandomForestClassifier(n_estimators=100, random_state=64)
_ = ucihd_rf.fit(ucihd_X_train, ucihd_y_train)

ucihd_rf_yhat = ucihd_rf.predict_proba(ucihd_X_test)[:,1]
ucihd_rf_pred = ucihd_rf.predict(ucihd_X_test)

print(classification_report(ucihd_y_test, ucihd_rf_pred))
              precision    recall  f1-score   support

           0       0.82      0.84      0.83        50
           1       0.80      0.78      0.79        41

    accuracy                           0.81        91
   macro avg       0.81      0.81      0.81        91
weighted avg       0.81      0.81      0.81        91
print(roc_auc_score(ucihd_y_test, ucihd_rf_yhat))
0.9004878048780488

As one can see RF performs very well on this dataset.

To explain a model trained with numerical features, lime by default will discretize continous variables into quantiles for ease of interpretation. Discretization is done using statistics derived from the training dataset.

from lime.lime_tabular import LimeTabularExplainer

cat_ind = [i for i, col in enumerate(ucihd_2.columns) if "_" in col]
ucihd_rf_explainer = LimeTabularExplainer(
  ucihd_X_train.values, class_names=["Negative", "Positive"],
  feature_names=ucihd_2.columns,
  categorical_features=cat_ind)

ucihd_rf_tp_idx = np.where(np.logical_and(ucihd_rf_pred == 1, ucihd_y_test == 1))[0]
ucihd_rf_fp_idx = np.where(np.logical_and(ucihd_rf_pred == 1, ucihd_y_test == 0))[0]

# We take one true positive and one false positive for examples.
ucihd_rf_tp_exp = ucihd_rf_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_tp_idx[0]], ucihd_rf.predict_proba, num_features=4)
ucihd_rf_fp_exp = ucihd_rf_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_fp_idx[0]], ucihd_rf.predict_proba, num_features=4)

ucihd_rf_tp_exp.save_to_file("/tmp/explain_tab_rf_tp.html")
ucihd_rf_fp_exp.save_to_file("/tmp/explain_tab_rf_fp.html")

Following the same idea in our discussion on text classifiers, we choose two examples, one true positive and the other false positive, from the RF predictions to demonstrate explanation modeling.

A True Positive Prediction Explained


The explanation suggests several dominant features toward the positive. For categoricals each category serves as individual contribution for explanation. This is a natural consequence of one-hot encoding in our feature space.

A False Positive Prediction Explained


For the false positive case, the model is less confident. There are indeed more features driving negatively. But one strong positive contribution from the feature ca (number of major vessels colored by flouroscopy) cancel out the entire negative driving forces.

3.2.2 Explain Gradient Boosting Trees

Gradient boosting trees (GBT) is a powerful model family proven to work exceptionally well in many different applications. Yet due to its ensembling nature, GBT is also hard to intrepret in general.

Here we demo lightgbm’s implementation of GBT with LIME explanation.

import lightgbm as lgb

ucihd_tr = lgb.Dataset(ucihd_X_train, label=ucihd_y_train)
ucihd_te = lgb.Dataset(ucihd_X_test, label=ucihd_y_test)

ucihd_lgb_params = {
  "learning_rate": .01,
  "boosting_type": "gbdt",
  "objective": "binary",
  "metric": ["binary_logloss", "auc"],
  "num_leaves": 8,
  "max_depth": 3,
  "min_data_per_leaf": 5,
  "verbose": -1,
  "seed": 64
}

ucihd_bst = lgb.train(
  params=ucihd_lgb_params,
  num_boost_round=300, early_stopping_rounds=20,
  train_set=ucihd_tr, valid_sets=[ucihd_te],
  verbose_eval=10)
Training until validation scores don't improve for 20 rounds
[10]    valid_0's binary_logloss: 0.655886  valid_0's auc: 0.775854
[20]    valid_0's binary_logloss: 0.628993  valid_0's auc: 0.785854
[30]    valid_0's binary_logloss: 0.60576   valid_0's auc: 0.81122
[40]    valid_0's binary_logloss: 0.585625  valid_0's auc: 0.824146
[50]    valid_0's binary_logloss: 0.569745  valid_0's auc: 0.826585
[60]    valid_0's binary_logloss: 0.556003  valid_0's auc: 0.826098
[70]    valid_0's binary_logloss: 0.542218  valid_0's auc: 0.839024
[80]    valid_0's binary_logloss: 0.532141  valid_0's auc: 0.843902
[90]    valid_0's binary_logloss: 0.524471  valid_0's auc: 0.84439
[100]   valid_0's binary_logloss: 0.516474  valid_0's auc: 0.85122
[110]   valid_0's binary_logloss: 0.510493  valid_0's auc: 0.85122
[120]   valid_0's binary_logloss: 0.506372  valid_0's auc: 0.852683
[130]   valid_0's binary_logloss: 0.498944  valid_0's auc: 0.851951
[140]   valid_0's binary_logloss: 0.493064  valid_0's auc: 0.854878
[150]   valid_0's binary_logloss: 0.49013   valid_0's auc: 0.856341
[160]   valid_0's binary_logloss: 0.487886  valid_0's auc: 0.853415
Early stopping, best iteration is:
[145]   valid_0's binary_logloss: 0.491347  valid_0's auc: 0.856341
ucihd_lgb_yhat = ucihd_bst.predict(ucihd_X_test)
ucihd_lgb_pred = (ucihd_lgb_yhat > .5).astype(int)

print(classification_report(ucihd_y_test, ucihd_lgb_pred))
              precision    recall  f1-score   support

           0       0.80      0.78      0.79        50
           1       0.74      0.76      0.75        41

    accuracy                           0.77        91
   macro avg       0.77      0.77      0.77        91
weighted avg       0.77      0.77      0.77        91
print(roc_auc_score(ucihd_y_test, ucihd_lgb_yhat))
0.8563414634146341

In this particular (rather small) dataset RF indeed outperforms GBT. As a matter of fact, based on existing benchmark a simple logistic regression may have a even higher score for this problem. Nevertheless, let’s move on to our explanation model with LIME:

def ucihd_lgb_predict_fn(x):
  # We need to output 2 columns for binary prob prediction.
  p = ucihd_bst.predict(x).reshape(-1, 1)
  return np.hstack((1 - p, p))

ucihd_lgb_explainer = LimeTabularExplainer(
  ucihd_X_train.values, class_names=["Negative", "Positive"],
  feature_names=ucihd_2.columns,
  categorical_features=cat_ind)

# We take the same examples previously explained in our RF explanation model.
ucihd_lgb_tp_exp = ucihd_lgb_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_tp_idx[0]], ucihd_lgb_predict_fn, num_features=4)
ucihd_lgb_fp_exp = ucihd_lgb_explainer.explain_instance(
  ucihd_X_test.iloc[ucihd_rf_fp_idx[0]], ucihd_lgb_predict_fn, num_features=4)

ucihd_lgb_tp_exp.save_to_file("/tmp/explain_tab_lgb_tp.html")
ucihd_lgb_fp_exp.save_to_file("/tmp/explain_tab_lgb_fp.html")

The behavior of GBT looks similar to that of RF in terms of these two examples.


In both case, the variable ca has a dominant impact on the final decision. The two modesl also share the same confusion against the negative example.


Optimized Categorical Encoding in lightgbm

This section is a digression on lightgbm usage.

Since lime’s API requires us to prepare our dataset in one-hot encoding representation, our lightgbm code use the same data pipeline as in scikit-learn random forest. But that is actually not optimized for lightgbm. The following code chunk showcases the best practice of encoding categoricals in lightgbm: We don’t encode them at all!

# We leave both missings and categoricals as-is in the dataset.
ucihd_train, ucihd_test = train_test_split(ucihd, test_size=.3, random_state=64)
ucihd_tr = lgb.Dataset(
  ucihd_train.drop("label", axis=1), label=ucihd_train["label"],
  categorical_feature=categorical_attr,
  free_raw_data=False)
ucihd_te = lgb.Dataset(
  ucihd_test.drop("label", axis=1), label=ucihd_test["label"],
  categorical_feature=categorical_attr,
  free_raw_data=False)

ucihd_bst_2 = lgb.train(
  params=ucihd_lgb_params,
  num_boost_round=300, early_stopping_rounds=20,
  train_set=ucihd_tr, valid_sets=[ucihd_te],
  verbose_eval=-1)
Training until validation scores don't improve for 20 rounds
Early stopping, best iteration is:
[94]    valid_0's binary_logloss: 0.519726  valid_0's auc: 0.852683
ucihd_lgb_yhat = ucihd_bst_2.predict(ucihd_test.drop("label", axis=1))
ucihd_lgb_pred = (ucihd_lgb_yhat > .5).astype(int)

print(roc_auc_score(ucihd_test["label"], ucihd_lgb_yhat))
0.8526829268292683

To summarize, There are two very special properties about lightgbm algorithm. lightgbm treats missings natively as a special tree split point. This allows us to keep the original missing as is and in many cases can result in better accuracy than imputation.7

In addition, lightgbm encodes categorical variables internally in a more efficient way. So we don’t even need to do one-hot encoding on our own. Of course in this tiny dataset we won’t see any noticable difference. But for large applications the performance impact can be huge. Whatever, by skipping one-hot encoding pipeline our code can be much neater as well.

3.3 On Image Classifier

TODO: Use a pre-trained model?

4 Shapley Regression Values

TODO: Theory Briefing here.

5 SHAP

Lundberg and Lee (2017) propose SHAP (SHapley Additive exPlanations), yet another additive feature attribution method for model explainability. It is a more general approach where LIME is indeed only a special case of it. Just like LIME, in theory it can be applied to any machine learning model, but comes with a customized fast implementation particularly for gradient boosting trees (GBT). It supports APIs of well-known GBT libraries such as xgboost, lightgbm, and catboost.

The interpretability provided by SHAP is again local. It assigns each feature an importance value for a particular prediction. Hence it provides for any given model prediction what may be the driving force for the model to make such prediction.

shap also comes with more visualization methods for feature investigation, especially for feature interaction exploration.

TODO: Theory Briefing here.

5.1 On Text Classifiers

5.1.1 Explain Random Forest

shap.TreeExplainer is optimized for GBT but not RF. For model with high dimensionality like a bag-of-words model it will suffer from high computation cost for non-GBT model. Hence we will skip the discussion on RF and move forward to a GBT implementation.

5.1.2 Explain Gradient Boosting Trees

In the previous section we didn’t train a GBT for the text classification problem. So let’s quickly build one such model first (with the same TF-IDF vectorization as we did for the RF model).

# lightgbm does not allow utf-8 encoded feature names.
# Since important tokens are most likely ascii-compatible for our dataset,
# we simply strip non-ascii as a workaround for this exercise.
def remove_non_ascii(s):
  return "".join([i if ord(i) < 128 else "_" for i in s])

sorted_vocab_ascii = [remove_non_ascii(v) for v in sorted_vocab]

imdb_X_tr = lgb.Dataset(imdb_X_train, label=imdb_y_train, feature_name=sorted_vocab_ascii)
imdb_X_te = lgb.Dataset(imdb_X_test, label=imdb_y_test, feature_name=sorted_vocab_ascii)

imdb_lgb_params = {
  "learning_rate": .05,
  "boosting_type": "gbdt",
  "objective": "binary",
  "metric": ["binary_logloss", "auc"],
  "num_leaves": 16,
  "max_depth": 4,
  "min_data_per_leaf": 20,
  "verbose": -1
}

imdb_lgb_model_file = os.path.join(model_dir, "text_clf_lgb.txt")

# Save/reload model to save notebook rendering time.
if os.path.exists(imdb_lgb_model_file):
  # Parameters are not loaded back? (Which cause the subsequent call to shap_values fail.)
  # https://github.com/microsoft/LightGBM/issues/2613
  # As a workaround we pass the same parameters to re-construct the model.
  imdb_bst = lgb.Booster(model_file=imdb_lgb_model_file, params=imdb_lgb_params)
else:
  imdb_bst = lgb.train(
    params=imdb_lgb_params,
    num_boost_round=1000, early_stopping_rounds=20,
    train_set=imdb_X_tr, valid_sets=[imdb_X_te],
    verbose_eval=100)
  _ = imdb_bst.save_model(imdb_lgb_model_file)
Training until validation scores don't improve for 20 rounds
[100]   valid_0's binary_logloss: 0.479194  valid_0's auc: 0.88184
[200]   valid_0's binary_logloss: 0.424974  valid_0's auc: 0.906732
[300]   valid_0's binary_logloss: 0.394577  valid_0's auc: 0.918715
[400]   valid_0's binary_logloss: 0.374584  valid_0's auc: 0.925959
[500]   valid_0's binary_logloss: 0.359882  valid_0's auc: 0.930936
[600]   valid_0's binary_logloss: 0.348809  valid_0's auc: 0.934481
[700]   valid_0's binary_logloss: 0.340231  valid_0's auc: 0.937016
[800]   valid_0's binary_logloss: 0.333412  valid_0's auc: 0.938953
[900]   valid_0's binary_logloss: 0.327711  valid_0's auc: 0.94053
[1000]  valid_0's binary_logloss: 0.323358  valid_0's auc: 0.94162
Did not meet early stopping. Best iteration is:
[1000]  valid_0's binary_logloss: 0.323358  valid_0's auc: 0.94162
imdb_lgb_yhat = imdb_bst.predict(imdb_X_test)
imdb_lgb_pred = (imdb_lgb_yhat > .5).astype(int)

print(classification_report(imdb_y_test, imdb_lgb_pred))
              precision    recall  f1-score   support

           0       0.88      0.85      0.86     12500
           1       0.85      0.88      0.87     12500

    accuracy                           0.86     25000
   macro avg       0.86      0.86      0.86     25000
weighted avg       0.86      0.86      0.86     25000
print(roc_auc_score(imdb_y_test, imdb_lgb_yhat))
0.9416203136

Based on the testing AUC score we find out that GBT performs comparably to neural network models.

Just like RF we will have access to the overall feature importance with a GBT model:8

ax = lgb.plot_importance(imdb_bst, max_num_features=20)
plt.show()

The global feature ranking reveals some highly ranked features to be meaningless on its own. Especially the word it. But as discussed earlier we shouldn’t over-interpret the ranks without a proper explanation modeling.

Since shap.TreeExplainer is customized for GBT for speed, we can feed in all testing examples to calculate all shap values at once.

import shap

# Sparse matrix is supported by shap for lightgbm models.
imdb_lgb_explainer = shap.TreeExplainer(imdb_bst)
imdb_lgb_shap_values = imdb_lgb_explainer.shap_values(imdb_X_test)

def imdb_lgb_shap_plot(test_id, matplotlib=True):
  shap_plt = shap.force_plot(
    imdb_lgb_explainer.expected_value[1],
    imdb_lgb_shap_values[1][test_id,:],
    imdb_X_test[test_id,:].toarray(),  # We still need a dense matrix here.
    feature_names=sorted_vocab,
    matplotlib=matplotlib
  )
  return shap_plt

Global Importance

One advantage of shap on GBT models is the capability of traverse through all the testing examples due to its efficiency. So we can based on all the resulting shap values to derive a global feature importance judged by their average shap values (contributions). Note that this is different from the loss/impurity or split time-based feature ranking derived from RF/GBT during training. It is an aggregation from all local prediction explanations (contributions) during testing data inference.

shap.summary_plot(imdb_lgb_shap_values, imdb_X_test, feature_names=sorted_vocab,
                  plot_type="bar", max_display=20, show=False, plot_size=.25)
plt.show()

As we can see, the ranking based on shap values for testing set will be in general different from the ranking based on training split. And it is more interpretable: Features with higher rank literally have averagely higher impact on the testing dataset. Also the ranking can be conditioned on labels.

Local Explanation

The most important application of shap still lies on instance-level explanation. We stick to the previous two reviews. For the review that RF correctly label positive, we have the shap explanation with the following visualization:

imdb_lgb_shap_plot(imdb_rf_tp_idx[0])

Note that by default shap for lightgbm shows log-odds rather than probability in the plot. So a positive value indicates a positive prediction, otherwise negative.

To verify this:

def to_log_odds(p):
  return np.log(p / (1 - p))

def to_p(log_odds):
  return np.exp(log_odds)/(1 + np.exp(log_odds))

# Take the first true positive to examine:
p = imdb_bst.predict(imdb_X_test[imdb_rf_tp_idx[0],:].toarray())
print(p)
[0.71683258]
print(to_log_odds(p))  # This is the reported number on the default shap plot.
[0.92880398]

For any given prediction, the shap values of all features should sum up to the difference between the predicted log-odds and the expected log-odds. To verify this on the specific positive example:

expected_log_odds = imdb_lgb_explainer.expected_value[1]
predicted_log_odds = to_log_odds(p)

print(predicted_log_odds - expected_log_odds)  # The difference.
[1.09763611]
shap_v = pd.DataFrame({
  "token": sorted_vocab,
  "shap_value": imdb_lgb_shap_values[1][imdb_rf_tp_idx[0],:],
  "tfidf": np.squeeze(imdb_X_test[imdb_rf_tp_idx[0]].toarray())
})
shap_v = shap_v.sort_values("shap_value", ascending=False)
print(shap_v)  # Shap values of all features for the example.
            token  shap_value     tfidf
8464   incredible    0.469118  0.138549
9893         love    0.358313  0.076663
4420   definitely    0.267002  0.109114
1420          bad    0.200221  0.000000
728          also    0.188378  0.066295
...           ...         ...       ...
8908           it   -0.135065  0.031411
1773       better   -0.136536  0.075703
7329        great   -0.173293  0.000000
14932       silly   -0.259718  0.125069
11305     nothing   -0.725885  0.084064

[18518 rows x 3 columns]
print(shap_v.shap_value.sum())  # The sum of shap values.
1.0976361111226303

From the entire shap values we can know for example that the absence of great contributes negatively, and the presence of love contributes positively, to the final prediction.

imdb_lgb_shap_plot(imdb_rf_fp_idx[0])

For the false positive case, similar to RF, the word great play a big role in shaping the GBT prediction toward positive.

5.1.3 Explain Neural Nets with Word Embeddings

As of 2019-12-11 shap.DeepExplainer does not yet support TF 2.0.9 And shap.GradientExplainer is not well documented yet for TF 2.0. So we will use the shap.KernelExplainer which is a implementation-agnostic explainer in shap. The compromise is that it will run very slow for each prediction.

imdb_exp_ind = np.array([imdb_rf_tp_idx[0], imdb_rf_fp_idx[0]])
# KernelExplainer.
def mm(X):
  return imdb_tr.predict_proba(X)[:,1]

imdb_nn_shap_explainer = shap.KernelExplainer(mm, seq_train_padded[:100])
# This is VERY slow...
#imdb_nn_kernel_shap_values = imdb_nn_shap_explainer.shap_values(seq_test_padded[imdb_exp_ind])
# TODO:
# Contribution is attributed to original sequence input.
# In order to make explanation readable,
# we need to map each position to original word id then to word.
# TODO: Makje sure everything works here.

# shap does not support keras model in scikit-learn wrapper.
# Let's re-build the model and retain its Sequental class.
dl_model = model_fn()
metrics = dl_model.fit(
  x=seq_train_padded, y=imdb_y_train,
  batch_size=256, epochs=20,
  validation_data=(seq_test_padded, imdb_y_test),
  validation_steps=20,
  callbacks=[
    tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=2),
    tf.keras.callbacks.ModelCheckpoint(tr_model_file, monitor="val_loss", save_best_only=True)
  ],
  verbose=0)

# DeepExplainer.
dl_shap_explainer = shap.DeepExplainer(dl_model, seq_train_padded)  # Wont' work.

# GradientExplainer.
imdb_nn_shap_explainer = shap.GradientExplainer(dl_model, seq_train_padded[:100])

imdb_nn_shap_explainer = shap.GradientExplainer(
  (imdb_tr.layers[0].input, imdb_tr.layers[-1].output),  # Not working for TF 2.0.
  seq_train_padded[:100])
imdb_nn_shap_explainer.shap_values(seq_test_padded[:3])  # Error here.

5.2 On Tabular Data Classifier

We do the same exercise on the tabular dataset previously explained by lime.

5.2.1 Explain Random Forest

ucihd_rf_explainer = shap.TreeExplainer(ucihd_rf)
ucihd_rf_shap_values = ucihd_rf_explainer.shap_values(ucihd_X_test)

def ucihd_rf_shap_plot(test_id, matplotlib=True):
  shap_plt = shap.force_plot(
    ucihd_rf_explainer.expected_value[1],
    ucihd_rf_shap_values[1][test_id,:],
    ucihd_X_test.iloc[[test_id]],
    matplotlib=matplotlib
  )
  return shap_plt

Global Feature Importance

From the global ranking we can confirm that variable ca is definitely an influential feature.

Split-time-based feature ranking
ucihd_rf_feat_imp = pd.Series(ucihd_rf.feature_importances_, index=ucihd_X_train.columns).sort_values()
ax = ucihd_rf_feat_imp.tail(10).plot(kind="barh")
plt.show()  # TODO: Adjust plot size.

Shap value feature ranking
shap.summary_plot(ucihd_rf_shap_values, ucihd_X_test,
                  plot_type="bar", max_display=10, show=False, plot_size=.25)
plt.show()

Feature Interaction

We can plot partial dependency based on shap values of two features over the entire testing dataset. For example, by knowing that ca is important, we’d like to further know how age can impact the contribution of ca across different examples.

shap.dependence_plot("age", ucihd_rf_shap_values[1], ucihd_X_test, interaction_index="ca")

The result suggests two things:

  1. The model will predict higher risk for older people
  2. ca has less impact for yonger people

Both can be examined by domain-experts to see if the model is learning the correct pattern that we expected or at least that we can reason.

Local Explanation

Note that for scikit-learn RF model by default shap reports probability instead of log-odds. Such behavior difference results from the optimization customized for GBT model family.

# The true positive case in RF.
ucihd_rf_shap_plot(ucihd_rf_tp_idx[0])

# The false positive case in RF.
ucihd_rf_shap_plot(ucihd_rf_fp_idx[0])

5.2.2 Explain Gradient Boosting Trees

For GBT we feed the model that is optimized, where categoricals are encoded internally without explicit one-hot encoding.

ucihd_lgb_explainer = shap.TreeExplainer(ucihd_bst_2)
ucihd_lgb_shap_values = ucihd_lgb_explainer.shap_values(ucihd_test.drop("label", axis=1))

def ucihd_lgb_shap_plot(test_id, matplotlib=True):
  shap_plt = shap.force_plot(
    ucihd_lgb_explainer.expected_value[1],
    ucihd_lgb_shap_values[1][test_id,:],
    ucihd_test.iloc[[test_id]].drop("label", axis=1),
    matplotlib=matplotlib
  )
  return shap_plt

Global Feature Importance

Split-time-based feature ranking
ax = lgb.plot_importance(ucihd_bst_2, max_num_features=10)
plt.show()

Shap value feature ranking
shap.summary_plot(ucihd_lgb_shap_values, ucihd_test.drop("label", axis=1),
                  plot_type="bar", max_display=10, show=False, plot_size=.25)
plt.show()

Feature Interaction
shap.dependence_plot("age", ucihd_lgb_shap_values[1],
                     ucihd_test.drop("label", axis=1), interaction_index="ca")

Local Explanation

ucihd_lgb_shap_plot(ucihd_rf_tp_idx[0])

ucihd_lgb_shap_plot(ucihd_rf_fp_idx[0])

5.2.3 The Impact of One-Hot Encoding On Explanation

As one may now realize, by explicitly one-hot-encode the categorical features we essentially split them into different features in their interpretable representation. This can be either good or bad, depending on the actual use case. From this particular aspect libary such as lightgbm provides the flexibility to allow us choose whether to do the one-hot encoding or not. So the way we want to construct the explanation model may well affect our implementation of the original model.

5.3 On Image Classifier

TODO: Use a pre-trained model?

6 Explainable Boosting Machine

Nori et al. (2019) publish the open source package interpret for a fast implementation of Generalized Additive Models with Pairwise Interactions, or GA2M (Lou et al. (2013)). As of 2019-12-11, interpret is still in its alpha release with limited documentation. The library contains two groups of modeling frameworks:

  • glassbox: explanable machine learning models
  • blackbox: machine learning explanation models (such as LIME and SHAP)

We’ve already covered the mainstream approach in the second group, i.e., models that approximate (locally) the original model (supposed to be a blackbox) for better explainability. The more interesting part of interpret is to bring about another type of model that is readily interpretable from its very origin, and yet still competitively accurate: the Explainable Boosting Machine, or EBM.

EBM is an additive model of the form:

\[ g(E(y)) = \beta_0 + \sum f_j (x_j) + \sum f_{ij}(x_i, x_j), \]

where \(g(\cdot)\) is a link function (sigmoid for binary classification, for an example), \(f_j\) is the feature function for the \(j\)-th feature, learned by a gradient boosting machine with only that feature at a time and in a round-robin fashion for all features. \(f_{ij}\) is a pairwise interaction feature function to further boost the accuracy of the model while remain interpretability.

The model is interpretable since the contribution of any individual feature can be directly quantified by their corresponding feature function \(f_j\). Such explanation can extend up to pairwise interaction if pairwise feature functions are also estimated.

TODO: How to detect pairwise interaction? Brief the FAST algorithm.

6.1 On Text/Image Data

EBM is not efficient for text dataset. Due to the algorithm’s design it will run too long for bag-of-words model since there are too many feature functions to estimate. If we fit a EBM with the movie review dataset, even if not a large dataset, we will encounter OOM (out-of-memory) issue. As a result, we will skip the discussion of EBM on a text classifier. (The same restriction applies to image dataset.)

6.2 On Tabular Data

ExplainableBoostingClassifier has a scikit-learn fashion API and hence is straightforward to use.

from interpret.glassbox import ExplainableBoostingClassifier

ucihd_ebm = ExplainableBoostingClassifier(
  n_estimators=16, feature_names=ucihd_2.columns, n_jobs=1)
_ = ucihd_ebm.fit(ucihd_X_train, ucihd_y_train)
WARNING: Logging before flag parsing goes to stderr.
W1211 00:54:05.923769 18132 all.py:334] Passing a numpy array to schema autogen when it should be dataframe.
ucihd_ebm_yhat = ucihd_ebm.predict_proba(ucihd_X_test)[:,1]
ucihd_ebm_pred = (ucihd_ebm_yhat > .5).astype(int)

print(classification_report(ucihd_y_test, ucihd_ebm_pred))
              precision    recall  f1-score   support

           0       0.88      0.86      0.87        50
           1       0.83      0.85      0.84        41

    accuracy                           0.86        91
   macro avg       0.86      0.86      0.86        91
weighted avg       0.86      0.86      0.86        91
print(roc_auc_score(ucihd_y_test, ucihd_ebm_yhat))
0.9341463414634146

The model performs very well on the heart disease dataset, outperforming both RF and GBT.

6.2.1 Global Explanation

interpret comes with a rich set of visualization tools (with plotly as its backend). Model explanation is divided into two groups: global and local.

For global explanation, we have access to both global feature importance and a per-feature feature contribution stats.

ucihd_ebm_global = ucihd_ebm.explain_global()
# All feature info:
print(ucihd_ebm_global.selector)

# Global feature importance.
           Name         Type  # Unique  % Non-zero
0           age   continuous        40       1.000
1      trestbps   continuous        45       1.000
2          chol   continuous       129       1.000
3       thalach   continuous        83       1.000
4       oldpeak   continuous        39       0.679
5         slope   continuous         3       1.000
6            ca   continuous         5       0.387
7       sex_0.0  categorical         2       0.335
8       sex_1.0  categorical         2       0.665
9       sex_nan  categorical         1       0.000
10       cp_1.0  categorical         2       0.080
11       cp_2.0  categorical         2       0.170
12       cp_3.0  categorical         2       0.292
13       cp_4.0  categorical         2       0.458
14       cp_nan  categorical         1       0.000
15      fbs_0.0  categorical         2       0.830
16      fbs_1.0  categorical         2       0.170
17      fbs_nan  categorical         1       0.000
18  restecg_0.0  categorical         2       0.505
19  restecg_1.0  categorical         2       0.014
20  restecg_2.0  categorical         2       0.481
21  restecg_nan  categorical         1       0.000
22    exang_0.0  categorical         2       0.670
23    exang_1.0  categorical         2       0.330
24    exang_nan  categorical         1       0.000
25     thal_3.0  categorical         2       0.571
26     thal_6.0  categorical         2       0.071
27     thal_7.0  categorical         2       0.349
28     thal_nan  categorical         2       0.009
ucihd_ebm_global.visualize().write_html("/tmp/ucihd_ebm_feat_imp.html", include_plotlyjs=False)
# Global contribution on age.
fid = ucihd_ebm_global.selector.Name.tolist().index("age")
ucihd_ebm_global.visualize(fid).write_html("/tmp/ucihd_ebm_age_imp.html", include_plotlyjs=False)

# Global contribution on trestbps.
fid = ucihd_ebm_global.selector.Name.tolist().index("trestbps")
ucihd_ebm_global.visualize(fid).write_html("/tmp/ucihd_ebm_trestbps_imp.html", include_plotlyjs=False)

# Global contribution on sex.
fid = ucihd_ebm_global.selector.Name.tolist().index("sex_0.0")
ucihd_ebm_global.visualize(fid).write_html("/tmp/ucihd_ebm_sex_imp.html", include_plotlyjs=False)

Feature Importance

Feature Contribution: Age

Feature Contribution: Resting Blood Pressure

Feature Contribution: Gender (Female)

6.2.2 Local Explanation

More importantly, we must be able to explain a specific model prediction locally. This can also be done easily with a couple of lines:

# Explain the same instances previously on RF.
ucihd_exp_ind = np.array([ucihd_rf_tp_idx[0], ucihd_rf_fp_idx[0]])

# We can feed multiple examples at the same time.
ucihd_ebm_local = ucihd_ebm.explain_local(
  ucihd_X_test.iloc[ucihd_exp_ind,:], ucihd_y_test[ucihd_exp_ind])
ucihd_ebm_local.visualize(0).write_html("/tmp/ucihd_ebm_exp_tp.html", include_plotlyjs=False)
ucihd_ebm_local.visualize(1).write_html("/tmp/ucihd_ebm_exp_fp.html", include_plotlyjs=False)

For the false positive case made by both RF and GBT, EBM is able to correctly predict the negative label. We still see a positive ca value contribute a lot toward a positive prediction, while EBM is able to also pick up several negative factors that jointly negate the positive impact, ending up with a correct prediction toward negative.

7 References

Abadi, Martı́n, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, et al. 2015. “TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems.” http://tensorflow.org/.

Lou, Yin, Rich Caruana, Johannes Gehrke, and Giles Hooker. 2013. “Accurate Intelligible Models with Pairwise Interactions.” In Proceedings of the 19th Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, 623–31. ACM.

Lundberg, Scott M, and Su-In Lee. 2017. “A Unified Approach to Interpreting Model Predictions.” In Advances in Neural Information Processing Systems 30, edited by I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, 4765–74. Curran Associates, Inc. http://papers.nips.cc/paper/7062-a-unified-approach-to-interpreting-model-predictions.pdf.

Maas, Andrew L., Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. 2011. “Learning Word Vectors for Sentiment Analysis.” In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 142–50. Portland, Oregon, USA: Association for Computational Linguistics. http://www.aclweb.org/anthology/P11-1015.

Nori, Harsha, Samuel Jenkins, Paul Koch, and Rich Caruana. 2019. “InterpretML: A Unified Framework for Machine Learning Interpretability.” arXiv Preprint arXiv:1909.09223.

Pedregosa, F., G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, et al. 2011. “Scikit-Learn: Machine Learning in Python.” Journal of Machine Learning Research 12: 2825–30.

Pennington, Jeffrey, Richard Socher, and Christopher Manning. 2014. “Glove: Global Vectors for Word Representation.” In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (Emnlp), 1532–43.

Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. 2016. “Why Should I Trust You?: Explaining the Predictions of Any Classifier.” In Proceedings of the 22nd Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, 1135–44. ACM.

Ushey, Kevin, JJ Allaire, and Yuan Tang. 2019. Reticulate: Interface to ’Python’. https://CRAN.R-project.org/package=reticulate.


  1. Some people will further differentiate explainability from interpretability, by characterizing interpretability as knowing how without knowing why, and explainability as not only knowing how but also knowing why. In this notebook for simplicity we don’t take such approach.↩︎

  2. In many such methods, the simplified input is the indicator of feature presence. One example: Shapley regression values.↩︎

  3. Keras also comes with the dataset preprocessed as integer sequences (from tf.keras.datasets import imdb).↩︎

  4. It will be much faster if we choose xgboost’s or lightgbm’s implementation of random forest. However, to demonstrate compatibility of lime with scikit-learn we purposely choose the slower implementation here.↩︎

  5. Note that, even for a single recurrent layer, training a RNN will be prohibitively slow without a GPU.↩︎

  6. V.A. Medical Center, Long Beach and Cleveland Clinic Foundation:Robert Detrano, M.D., Ph.D.↩︎

  7. xgboost is the first to introduce such missing treatment among all the GBT package. lightgbm follows.↩︎

  8. By default lightgbm calculates the importance by counting how many times a feature contributes to an optimal split during training. It also supports the impurity-based approach with argument importance_type set to "gain".↩︎

  9. https://github.com/slundberg/shap/issues/850.↩︎

LS0tCnRpdGxlOiAiT24gTW9kZWwgRXhwbGFpbmFiaWxpdHkiCnN1YnRpdGxlOiAiRnJvbSBMSU1FLCBTSEFQLCB0byBFeHBsYWluYWJsZSBCb29zdGluZyIKYXV0aG9yOgotIG5hbWU6IEt5bGUgQ2h1bmcKICBhZmZpbGlhdGlvbjoKZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJWQgJWIgJVknKWAgTGFzdCBVcGRhdGVkICgwOSBEZWMgMjAxOSBGaXJzdCBVcGxvYWRlZCkiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgaGlnaGxpZ2h0OiB0YW5nbwogICAgbnVtYmVyX3NlY3Rpb25zOiB5ZXMKICAgIHRoZW1lOiBwYXBlcgogICAgdG9jOiB5ZXMKICAgIHRvY19kZXB0aDogMwogICAgdG9jX2Zsb2F0OiB5ZXMKICAgIGluY2x1ZGVzOgogICAgICBpbl9oZWFkZXI6IC90bXAvbWV0YV9oZWFkZXIuaHRtbAogIGNvZGVfZG93bmxvYWQ6IHRydWUKYmlibGlvZ3JhcGh5OiBtb2RlbF9leHBsYWluLmJpYgpub2NpdGU6IHwKICBAcmV0aWN1bGF0ZQogIEBtYWFzLUV0QWw6MjAxMTpBQ0wtSExUMjAxMQogIEBzY2lraXQtbGVhcm4KICBAdGVuc29yZmxvdzIwMTUtd2hpdGVwYXBlcgphYnN0cmFjdDogfAogIE1vZGVsIGV4cGxhaW5hYmlsaXR5IGhhcyBnYWluZWQgbW9yZSBhbmQgbW9yZSBhdHRlbnRpb24gcmVjZW50bHkgYW1vbmcgbWFjaGluZSBsZWFybmluZyBwcmFjdGl0aW9uZXJzLiBFc3BlY2lhbGx5IHdpdGggdGhlIHBvcHVsYXJpemF0aW9uIG9mIGRlZXAgbGVhcm5pbmcgZnJhbWV3b3Jrcywgd2hpY2ggZnVydGhlciBwcm9tb3RlcyB0aGUgdXNlIG9mIGluY3JlYXNpbmdseSBjb21wbGljYXRlZCBtb2RlbHMgdG8gaW1wcm92ZSBhY2N1cmFjeS4gSW4gdGhlIHJlYWxpdHksIGhvd2V2ZXIsIG1vZGVsIHdpdGggdGhlIGhpZ2hlc3QgYWNjdXJhY3kgbWF5IG5vdCBiZSB0aGUgb25lIHRoYXQgY2FuIGJlIGRlcGxveWVkLiBUcnVzdCBpcyBvbmUgaW1wb3J0YW50IGZhY3RvciBhZmZlY3RpbmcgdGhlIGFkb3B0aW9uIG9mIGNvbXBsaWNhdGVkIG1vZGVscy4gSW4gdGhpcyBub3RlYm9vayB3ZSBnaXZlIGEgYnJpZWYgaW50cm9kdWN0aW9uIHRvIHNldmVyYWwgcG9wdWxhciBtZXRob2RzIG9uIG1vZGVsIGV4cGxhaW5hYmlsaXR5LiBBbmQgd2UgZm9jdXMgbW9yZSBvbiB0aGUgaGFuZHMtb24gd2hpY2ggZGVtb25zdHJhdGVzIGhvdyB3ZSBjYW4gYWN0dWFsbHkgZXhwbGFpbiBhIG1vZGVsLCB1bmRlciBhIHZhcmlldHkgb2YgdXNlIGNhc2VzLgotLS0KPCEtLUZvciBlcXVhdGlvbiByZWZlcmVuY2UgaW4gUm1kLi0tPgo8c2NyaXB0IHR5cGU9InRleHQveC1tYXRoamF4LWNvbmZpZyI+Ck1hdGhKYXguSHViLkNvbmZpZyh7CiAgVGVYOiB7IGVxdWF0aW9uTnVtYmVyczogeyBhdXRvTnVtYmVyOiAiQU1TIiB9IH0KfSk7Cjwvc2NyaXB0PgoKPCEtLSBFbWJlZCBsaW1lIGphdmFzY3JpcHQgbGlicmFyeSBmb3IgZXhwbGFuYXRpb24gdmlzdWFsaXphdGlvbi4gLS0+CjxzY3JpcHQgc3JjPSJsaW1lLmpzIj48L3NjcmlwdD4KCjwhLS0gRW1iZWQgcGxvdGx5IGphdmFzY3JpcHQgbGlicmFyeS4KICBUaGlzIGlzIHRoZSBiYWNrZW5kIGZvciBpbnRlcnByZXRNTCB2aXN1YWxpemF0aW9uLgotLT4KPHNjcmlwdCBzcmM9Ii4uLy4uLy4uL3NpdGVfbGlicy91dGlscy9wbG90bHktMS41MS4xLm1pbi5qcyI+PC9zY3JpcHQ+CgpgYGB7ciBtZXRhLCBpbmNsdWRlPUZBTFNFfQptZXRhX2hlYWRlcl9maWxlIDwtIGZpbGUoIi90bXAvbWV0YV9oZWFkZXIuaHRtbCIpCgojIEFkZCBvcGVuIGdyYXBoIG1ldGEuCm1ldGEgPC0gYygKICAnPG1ldGEgbmFtZT0iYXV0aG9yIiBjb250ZW50PSJLeWxlIENodW5nIj4nLAogICc8bWV0YSBwcm9wZXJ0eT0ib2c6dGl0bGUiIGNvbnRlbnQ9Ik9uIE1vZGVsIEV4cGxhaW5hYmlsaXR5OiBGcm9tIFNoYXAsIExpbWUsIHRvIEludGVycHJldGFibGUgQm9vc3RpbmciPicsCiAgJzxtZXRhIHByb3BlcnR5PSJvZzp0eXBlIiBjb250ZW50PSJhcnRpY2xlIj4nLAogICc8bWV0YSBwcm9wZXJ0eT0ib2c6dXJsIiBjb250ZW50PSJodHRwczovL2V2ZXJkYXJrLmdpdGh1Yi5pby9rOS9ub3RlYm9va3MvbWwvbW9kZWxfZXhwbGFpbi9tb2RlbF9leHBsYWluLm5iLmh0bWwiPicsCiAgJzxtZXRhIHByb3BlcnR5PSJvZzppbWFnZSIgY29udGVudD0iaHR0cHM6Ly9ldmVyZGFyay5naXRodWIuaW8vazkvYXNzZXRzL2FuZHJvaWRpZnkuanBnIj4nLAogICc8bWV0YSBwcm9wZXJ0eT0ib2c6ZGVzY3JpcHRpb24iIGNvbnRlbnQ9IkEgZGF0YSBzY2llbmNlIG5vdGVib29rIGFib3V0IG1hY2hpbmUgbGVhcm5pbmcgbW9kZWwgZXhwbGFpbmFiaWxpdHkuIj4nCikKY29udGVudHMgPC0gbWV0YQoKIyBBZGQgR2l0aHViIGNvcm5lci4KZ2l0aHViX2Nvcm5lcl9zdmcgPC0gIi4uLy4uLy4uL2Fzc2V0cy9naXRodWJfY29ybmVyLmh0bWwiCmdpdGh1Yl9jb3JuZXJfY29uZiA8LSBsaXN0KGdpdGh1Yl9saW5rPSJodHRwczovL2dpdGh1Yi5jb20vZXZlcmRhcmsvazkvdHJlZS9tYXN0ZXIvbm90ZWJvb2tzL21sL21vZGVsX2V4cGxhaW4iKQpjb250ZW50cyA8LSBjKGNvbnRlbnRzLCBzdHJpbmdyOjpzdHJfaW50ZXJwKHJlYWRMaW5lcyhnaXRodWJfY29ybmVyX3N2ZyksIGdpdGh1Yl9jb3JuZXJfY29uZikpCndyaXRlTGluZXMoY29udGVudHMsIG1ldGFfaGVhZGVyX2ZpbGUpCgpjbG9zZShtZXRhX2hlYWRlcl9maWxlKQpgYGAKCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQpsaWJyYXJ5KHJldGljdWxhdGUpCnIgPC0gdHJ5KHVzZV9weXRob24oU3lzLmdldGVudigiUFlUSE9OX1BBVEgiKSwgcmVxdWlyZWQ9VFJVRSksIHNpbGVudD1UUlVFKQppZiAoIGlzKHIsICJ0cnktZXJyb3IiKSApIHsKICByIDwtIHRyeSh1c2VfdmlydHVhbGVudihTeXMuZ2V0ZW52KCJQWVRIT05fUEFUSCIpLCByZXF1aXJlZD1UUlVFKSwgc2lsZW50PVRSVUUpCiAgaWYgKCBpcyhyLCAidHJ5LWVycm9yIikgKSB1c2VfY29uZGFlbnYoU3lzLmdldGVudigiUFlUSE9OX1BBVEgiKSwgcmVxdWlyZWQ9VFJVRSkKfQoKIyBVdGlsaXR5IHRvIHBvc3QtcHJvY2VzcyBodG1sIG91dHB1dC4KbGlicmFyeSh4bWwyKQoKd3JpdGVfbGltZV9qcyA8LSBmdW5jdGlvbihpbmZpbGUpIHsKICAjIGxpbWUgaHRtbCBvdXRwdXQgY29udGFpbnMgYSBodWdlIGpzIHN0cmluZywKICAjIHRvIHJlZHVjZSBub3RlYm9vayBmaWxlIHNpemUgd2Ugb25seSB3YW50IHRvIGRlY2xhcmUgdGhlIGpzIG9uY2UuCiAgb3V0ZmlsZSA8LSAibGltZS5qcyIKICBkb2MgPC0gYXNfbGlzdChyZWFkX2h0bWwoaW5maWxlKSkKICBqc19zdHIgPC0gZG9jJGh0bWwkaGVhZCRzY3JpcHRbWzFdXQogICMgVXNlIGg0IGZvciB0ZXh0IGV4YW1wbGUgaGVhZGVyIHRvIGF2b2lkIGJlaW5nIGluY2x1ZGVkIGluIHJtZCB0b2MuCiAganNfc3RyIDwtIGdzdWIoImgzIiwgImg0IiwganNfc3RyKQogIHdyaXRlTGluZXMoanNfc3RyLCBvdXRmaWxlLCB1c2VCeXRlcz1UUlVFKQp9CgpwYXJzZV9saW1lX2h0bWxfb3V0cHV0IDwtIGZ1bmN0aW9uKGluZmlsZSwgZXhjbHVkZV9qcz1UUlVFKSB7CiAgb3V0ZmlsZSA8LSB0ZW1wZmlsZSgpCiAgZG9jIDwtIHJlYWRfaHRtbChpbmZpbGUpCiAgaWYgKCBleGNsdWRlX2pzICkgeG1sX3JlbW92ZSh4bWxfY2hpbGQoZG9jKSkKICB3cml0ZV9odG1sKGRvYywgb3V0ZmlsZSkKICBvdXRmaWxlCn0KYGBgCgotLS0KClRoaXMgbm90ZWJvb2sgaXMgd3JpdHRlbiB3aXRoIFtgcmV0aWN1bGF0ZWBdKGh0dHBzOi8vZ2l0aHViLmNvbS9yc3R1ZGlvL3JldGljdWxhdGUpLAphIHBhY2thZ2UgdGhhdCBhbGxvd3MgaW50ZXItb3BlcmF0aW9uIGJldHdlZW4gUiBhbmQgUHl0aG9uLgoKLS0tCgojIE1vdGl2YXRpb24KCldoeSBkbyB3ZSBuZWVkIHRvIGV4cGxhaW4gYSBtYWNoaW5lIGxlYXJuaW5nIG1vZGVsPwpUaGUgYmVuZWZpdCBvZiBhbiBleHBsYW5hYmxlIG1vZGVsIGFnYWluc3QgYSBibGFjay1ib3ggbW9kZWwgaXMgZm9yIHRoZSBtb2RlbCB0byBiZSAqdHJ1c3RlZCouClRydXN0IGNhbiBiZSBpbXBvcnRhbnQgaW4gbWFueSByZWFsIGFwcGxpY2F0aW9ucyB3aGVyZSB0aGUgc3VjY2Vzc2Z1bCBkZXBsb3ltZW50IG9mIGEgbWFjaGluZSBsZWFybmluZyBtb2RlbCByZXF1aXJlcyB0aGUgdHJ1c3QgZnJvbSBlbmQgdXNlcnMuClNvbWV0aW1lcyB0cnVzdCBwbGF5cyBhIGV2ZW4gYmlnZ2VyIHJvbGUgdGhhbiBtb2RlbCBhY2N1cmFjeS4KCk90aGVyIHRoYW4gdHJ1c3QsCm1vZGVsIGV4cGxhaW5hYmlsaXR5IChvciBpbnRlcnByZXRhYmlsaXR5LCBpbnRlcmNoYW5nZWFibHkgdXNlZCBoZXJlYWZ0ZXIpIG1heSBhbHNvIGd1aWRlIHVzIGluIHRoZSBjb3JyZWN0IGRpcmVjdGlvbiB0byBmdXJ0aGVyIGltcHJvdmUgdGhlIG1vZGVsLgpeW1NvbWUgcGVvcGxlIHdpbGwgZnVydGhlciBkaWZmZXJlbnRpYXRlIGV4cGxhaW5hYmlsaXR5IGZyb20gaW50ZXJwcmV0YWJpbGl0eSwKYnkgY2hhcmFjdGVyaXppbmcgaW50ZXJwcmV0YWJpbGl0eSBhcyBrbm93aW5nIGhvdyB3aXRob3V0IGtub3dpbmcgd2h5LAphbmQgZXhwbGFpbmFiaWxpdHkgYXMgbm90IG9ubHkga25vd2luZyBob3cgYnV0IGFsc28ga25vd2luZyB3aHkuCkluIHRoaXMgbm90ZWJvb2sgZm9yIHNpbXBsaWNpdHkgd2UgZG9uJ3QgdGFrZSBzdWNoIGFwcHJvYWNoLl0KCkluIGdlbmVyYWwsCmxpbmVhciBtb2RlbCBpcyBtb3JlIGludGVycHJldGFibGUgdGhhbiBub24tbGluZWFyIG1vZGVsLgpCdXQgdGhlIGZvcm1lciBhbHNvIHN1ZmZlcnMgZnJvbSBsb3dlciBhY2N1cmFjeS4KTW9yZSBhZHZhbmNlZCBhbmQgaGVuY2UgY29tcGxpY2F0ZWQgbW9kZWwgdXN1YWxseSBoYXMgd29yc2UgaW50ZXJwcmV0YWJpbGl0eS4KCk9uZSBzaG91bGQgbm90IGNvbmZ1c2UgbW9kZWwgZXhwbGFpbmFiaWxpdHkgd2l0aCB0aGUgYWN0dWFsIGNhdXNhbGl0eS4KQmVpbmcgYWJsZSB0byBleHBsYWluIGEgbW9kZWwgZG9lc24ndCBtZWFuIHRoYXQgd2UgY2FuIGlkZW50aWZ5IGFueSBncm91bmQtdHJ1dGggY2F1c2FsIHJlbGF0aW9uIGJlaGluZCB0aGUgbW9kZWwuCk1vZGVsIGV4cGxhaW5hYmlsaXR5IGlzIGZvciBhbmQgb25seSBmb3IgdGhlIG1vZGVsLApidXQgbm90IGZvciB0aGUgZmFjdHMgd2UnZCBsaWtlIHRvIG1vZGVsLgpOZXZlcnRoZWxlc3MsCnVuZGVyc3RhbmQgaG93IHdlIGNhbiByZWFzb24gdGhlIG1vZGVsIGRlZmluaXRlbHkgd2lsbCBoZWxwIHVzIGJldHRlciBtb2RlbCB0aGUgYWN0dWFsIHBhdHRlcm4gYmVoaW5kIHRoZSBzY2VuY2UuCgpJbiB0aGlzIG5vdGVib29rIHdlIHdpbGwgd2FsayB0aHJvdWdoIDMgcG9wdWxhciBhcHByb2FjaGVzIG9mIG1vZGVsIHByZWRpY3Rpb24gZXhwbGFuYXRpb24sCmVhY2ggb2YgdGhlbSBjb21lcyB3aXRoIGEgZGVkaWNhdGVkIFB5dGhvbiBwYWNrYWdlOgoKMS4gW2BzaGFwYF0oaHR0cHM6Ly9naXRodWIuY29tL3NsdW5kYmVyZy9zaGFwKQoyLiBbYGxpbWVgXShodHRwczovL2dpdGh1Yi5jb20vbWFyY290Y3IvbGltZSkKMy4gW2BpbnRlcnByZXRgXShodHRwczovL2dpdGh1Yi5jb20vaW50ZXJwcmV0bWwvaW50ZXJwcmV0KQoKIyBFeHBsYW5hdGlvbiBNb2RlbHMKCkFuIGV4cGxhbmF0aW9uIG1vZGVsICRnKHgpJCBpcyBhbiAqaW50ZXJwcmV0YWJsZSBhcHByb3hpbWF0aW9uKiBvZiB0aGUgb3JpZ2luYWwgbW9kZWwgJGYoeCkkLgpJdHMgc29sZSBwdXJwb3NlIGlzIHRvIGdpdmUgZXh0cmEgZXhwbGFpbmFiaWxpdHkgdGhlIG9yaWdpbmFsIG1vZGVsIGZhaWxzIHRvIHByb3ZpZGUsCmR1ZSB0byBpdHMgb3duIGNvbXBsZXhpdHkuCgpUaGUgZ2VuZXJhbCBpZGVhIGlzIHRvIHVzZSBhIHNpbXBsaWZpZWQgaW5wdXQgJHhccHJpbWUkIHN1Y2ggdGhhdCAkeCA9IGhfeCh4XHByaW1lKSQsCndoZXJlICRoX3goXGNkb3QpJCBpcyBhIG1hcHBpbmcgZnVuY3Rpb24gZm9yIGFueSBnaXZlbiByYXcgaW5wdXQgJHgkLgpUaGVuIHRoZSBpbnRlcnByZXRhYmxlIGFwcHJveGltYXRpb24gY2FuIGJlIHdyaXR0ZW4gYXM6CgokJApnKHhccHJpbWUpIFxhcHByb3ggZihoX3goeFxwcmltZSkpLgokJAoKVGhlICphZGRpdGl2ZSBmZWF0dXJlIGF0dHJpYnV0aW9uIG1ldGhvZHMqIHNwZWNpZnkgdGhlIGV4cGxhbmF0aW9uIG1vZGVsIG9mIHRoZSBmb2xsb3dpbmcgZm9ybToKCiQkCmcoeFxwcmltZSkgPSBccGhpXzAgKyBcc3VtX3tpID0gMX1ebSBccGhpX2kgeF9pXHByaW1lLAokJAoKd2hlcmUgJG0kIGlzIHRvdGFsIG51bWJlciBvZiBzaW1wbGlmaWVkIGZlYXR1cmVzLAokeFxwcmltZSBcaW4gXHswLCAxXH0kIHNpbXBseSBhbiBpbmRpY2F0b3IuXltJbiBtYW55IHN1Y2ggbWV0aG9kcywgdGhlIHNpbXBsaWZpZWQgaW5wdXQgaXMgdGhlIGluZGljYXRvciBvZiBmZWF0dXJlIHByZXNlbmNlLiBPbmUgZXhhbXBsZTogU2hhcGxleSByZWdyZXNzaW9uIHZhbHVlcy5dCkFwcGFyZW50bHksCnRoZSBjaG9pY2Ugb2YgYW4gYWRkaXRpdmUgbW9kZWwgaXMgZm9yIChsaW5lYXIpIGludHJlcHJldGFiaWxpdHkuClRoZSBzaW1wbGlmaWVkIGZlYXR1cmVzIGFyZSBhbiAqaW50ZXJwcmV0YWJsZSByZXByZXNlbnRhdGlvbiogb2YgdGhlIG9yaWdpbmFsIG1vZGVsIGZlYXR1cmVzLgoKIyBMSU1FCgpPbmUgdmVyeSBwb3B1bGFyIHN1Y2ggYWJvdmUgYWRkaXRpdmUgbW9kZWwgaXMgTElNRSAoQHJpYmVpcm8yMDE2c2hvdWxkKS4KTElNRSBzdGFuZHMgZm9yICoqTG9jYWwgSW50ZXJwcmV0YWJsZSBNb2RlbC1BZ25vc3RpYyBFeHBsYW5hdGlvbnMuKioKQXMgaXRzIGZ1bGwgbmFtZSBzdWdnZXN0cywKTElNRSBjYW4gYmUgYXBwbGllZCB0byAqYW55KiBtYWNoaW5lIGxlYXJuaW5nIG1vZGVsLgpMSU1FIGFjaGlldmVzIHByZWRpY3Rpb24tbGV2ZWwgaW50ZXJwcmV0YWJpbGl0eSBieSBhcHByb3htaWF0aW5nIHRoZSBvcmlnaW5hbCBtb2RlbCB3aXRoIGFuIGV4cGxhbmF0aW9uIG1vZGVsIGxvY2FsbHkgYXJvdW5kIHRoYXQgcHJlZGljdGlvbi4KCioqVE9ETzogQWRkIHRoZW9yeSBicmllZmluZyBoZXJlLioqCgojIyBPbiBUZXh0IENsYXNzaWZpZXJzCgpGb3IgdGV4dCBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLAp0aGUgbW9zdCBzdHJhaWdodGZvcndhcmQgaW50ZXJwcmV0YWJsZSByZXByZXNlbnRhdGlvbiBvZiB0aGUgbW9kZWwgZmVhdHVyZXMgd2lsbCBiZSBhIGJpbmFyeSBpbmRpY2F0b3IgdmVjdG9yIG9mIGJhZyBvZiB3b3Jkcy4KU28gdGhlIGV4cGxhbmF0aW9uIG1vZGVsIHdpbGwgdHJ5IHRvIHJlYXNvbiB3aGljaCB3b3JkIG9yIHRva2VuIGlzIGRyaXZpbmcgdGhlIHByZWRpY3Rpb24gaW4gd2hhdCBkaXJlY3Rpb24uCkFuZCB0aGlzIGlzIHRydWUgbm8gbWF0dGVyIHRoZSBmb3JtIG9mIHRoZSBvcmlnaW5hbCBtb2RlbCBmZWF0dXJlLgpNYXkgaXQgYmUgYSB3b3JkIGNvdW50IG1hdHJpeCwKYSB0ZXJtIGZyZXF1ZW5jeS1pbnZlcnNlIGRvY3VtZW50IGZyZXF1ZW5jeSAoVEYtSURGKSBtYXRyaXgsCm9yIG51bWVyaWNhbCBlbWJlZGRpbmdzLgoKSW4gdGhlIGZvbGxvd2luZyB3ZSB3aWxsIHVzZSBbTGFyZ2UgTW92aWUgUmV2aWV3IERhdGFzZXRdKGh0dHBzOi8vYWkuc3RhbmZvcmQuZWR1L35hbWFhcy9kYXRhL3NlbnRpbWVudC8pIHRvIGRvIGEgYmluYXJ5IHNlbnRpbWVudCBjbGFzc2lmaWNhdGlvbiBleGVyY2lzZS4KV2Ugd2lsbCB1c2UgbWFjaGluZSBsZWFybmluZyBsaWJyYXJpZXMgc3VjaCBhcyBgc2Npa2l0LWxlYXJuYCBhbmQgYHRlbnNvcmZsb3dgIHRvIHF1aWNrbHkgYnVpbGQgbW9kZWxzIGFuZCB1c2UgYGxpbWVgIHRvIGV4cGVyaW1lbnQgZXhwbGFuYXRpb24gbW9kZWxpbmcuCgpgYGB7cHl0aG9uIGltcG9ydF9zb21lfQppbXBvcnQgb3MKaW1wb3J0IGxvZ2dpbmcKbG9nZ2luZy5nZXRMb2dnZXIoInRlbnNvcmZsb3ciKS5zZXRMZXZlbChsb2dnaW5nLkVSUk9SKQppbXBvcnQgd2FybmluZ3MKd2FybmluZ3Muc2ltcGxlZmlsdGVyKGFjdGlvbj0iaWdub3JlIiwgY2F0ZWdvcnk9VXNlcldhcm5pbmcpCndhcm5pbmdzLnNpbXBsZWZpbHRlcihhY3Rpb249Imlnbm9yZSIsIGNhdGVnb3J5PUZ1dHVyZVdhcm5pbmcpCgppbXBvcnQgbWF0cGxvdGxpYi5weXBsb3QgYXMgcGx0CmltcG9ydCBudW1weSBhcyBucAppbXBvcnQgcGFuZGFzIGFzIHBkCgppbXBvcnQgdGVuc29yZmxvdyBhcyB0ZgpwcmludCh0Zi5fX3ZlcnNpb25fXykKaWYgdGYudGVzdC5pc19ncHVfYXZhaWxhYmxlKCk6CiAgcHJpbnQodGYudGVzdC5ncHVfZGV2aWNlX25hbWUoKSkKCmltcG9ydCBza2xlYXJuCmZyb20gc2tsZWFybi5mZWF0dXJlX2V4dHJhY3Rpb24udGV4dCBpbXBvcnQgVGZpZGZWZWN0b3JpemVyCmZyb20gc2tsZWFybi5lbnNlbWJsZSBpbXBvcnQgUmFuZG9tRm9yZXN0Q2xhc3NpZmllcgpmcm9tIHNrbGVhcm4ucGlwZWxpbmUgaW1wb3J0IG1ha2VfcGlwZWxpbmUKZnJvbSBza2xlYXJuLm1ldHJpY3MgaW1wb3J0IGNsYXNzaWZpY2F0aW9uX3JlcG9ydCwgcm9jX2F1Y19zY29yZQpmcm9tIHNrbGVhcm4ubW9kZWxfc2VsZWN0aW9uIGltcG9ydCB0cmFpbl90ZXN0X3NwbGl0CmltcG9ydCBqb2JsaWIKCnByaW50KHNrbGVhcm4uX192ZXJzaW9uX18pCmBgYAoKYGBge3B5dGhvbiBta2Rpcn0KIyBDcmVhdGUgbW9kZWwgZGlyIHRvIGNhY2hlIGFsbCBtb2RlbHMgdHJhaW5lZCBpbiB0aGUgbm90ZWJvb2suCm1vZGVsX2RpciA9ICJtb2RlbHMiCmlmIG5vdCBvcy5wYXRoLmV4aXN0cyhtb2RlbF9kaXIpOgogICAgb3MubWFrZWRpcnMobW9kZWxfZGlyKQoKIyBEaXJlY3RvcnkgdG8gY2FjaGUgZGF0YXNldC4KaG9tZSA9IG9zLnBhdGguZXhwYW5kdXNlcigifiIpCmNhY2hlX2RpciA9IG9zLnBhdGguam9pbihob21lLCAiLmtlcmFzIikKYGBgCgpGaXJzdCwKd2UgcHJlcGFyZSB0aGUgbW92aWUgcmV2aWV3IGRhdGFzZXQuXltLZXJhcyBhbHNvIGNvbWVzIHdpdGggdGhlIGRhdGFzZXQgcHJlcHJvY2Vzc2VkIGFzIGludGVnZXIgc2VxdWVuY2VzIChgZnJvbSB0Zi5rZXJhcy5kYXRhc2V0cyBpbXBvcnQgaW1kYmApLl0KCmBgYHtweXRob24gbWF5YmVfZG93bmxvYWRfaW1kYiwgcmVzdWx0cz0iaGlkZSJ9CmltcG9ydCB0ZW5zb3JmbG93X2RhdGFzZXRzIGFzIHRmZHMKCiMgTG9hZCB0aGUgZGF0YSBhcyB0Zi5kYXRhLkRhdGFzZXQuCmltZGIgPSB0ZmRzLmxvYWQobmFtZT0iaW1kYl9yZXZpZXdzIiwgYXNfc3VwZXJ2aXNlZD1UcnVlLAogICAgICAgICAgICAgICAgIGRhdGFfZGlyPW9zLnBhdGguam9pbihob21lLCAidGVuc29yZmxvd19kYXRhc2V0cyIpKQpgYGAKClRoZSBkYXRhc2V0IGlzIGEgcGVyZmVjdGx5IGJhbGFuY2VkIGRhdGFzZXQgd2l0aCA1MCwwMDAgZXhhbXBsZXMsCmhhbGYgZm9yIHBvc2l0aXZlIGFuZCBoYWxmIGZvciBuZWdhdGl2ZSBzZW50aW1lbnQuCgpgYGB7cHl0aG9uIHByZXBhcmVfaW1kYn0KIyBFeHRyYWN0IGFsbCB0ZXh0cyBhcyBsaXN0IHNpbmNlIHdlIHdhbnQgdG8gdXNlIGxpYnJhcmllcyBvdGhlciB0aGFuIHRlbnNvcmZsb3cgYXMgd2VsbC4KIyBBbmQgc2luY2UgdGhpcyBpcyBhIHNtYWxsIGRhdGFzZXQsIHdlIGRvbid0IGNhcmUgYWJvdXQgbWVtb3J5IHVzYWdlLgojIFdlIHNraXAgdGhlIHVzZSBvZiBhIGRhdGFzZXQgaXRlcmF0b3IuCmltZGJfcmV2aWV3c190cmFpbiA9IFtdCmltZGJfcmV2aWV3c190ZXN0ID0gW10KaW1kYl95X3RyYWluID0gW10KaW1kYl95X3Rlc3QgPSBbXQpmb3IgeCwgeSBpbiBpbWRiWyJ0cmFpbiJdLmJhdGNoKDEyOCk6CiAgaW1kYl9yZXZpZXdzX3RyYWluLmV4dGVuZCh4Lm51bXB5KCkpCiAgaW1kYl95X3RyYWluLmV4dGVuZCh5Lm51bXB5KCkpCmZvciB4LCB5IGluIGltZGJbInRlc3QiXS5iYXRjaCgxMjgpOgogIGltZGJfcmV2aWV3c190ZXN0LmV4dGVuZCh4Lm51bXB5KCkpCiAgaW1kYl95X3Rlc3QuZXh0ZW5kKHkubnVtcHkoKSkKCiMgVEYgd29ya3Mgb24gYnl0ZXMsIGJ1dCBzb21lIG90aGVyIHBhY2thZ2VzIG1heSBvbmx5IHdvcmsgb24gZGVjb2RlZCBzdHJpbmcuCmltZGJfcmV2aWV3c190cmFpbiA9IFtiLmRlY29kZSgidXRmOCIpIGZvciBiIGluIGltZGJfcmV2aWV3c190cmFpbl0KaW1kYl9yZXZpZXdzX3Rlc3QgPSBbYi5kZWNvZGUoInV0ZjgiKSBmb3IgYiBpbiBpbWRiX3Jldmlld3NfdGVzdF0KaW1kYl95X3RyYWluID0gbnAuYXJyYXkoaW1kYl95X3RyYWluKQppbWRiX3lfdGVzdCA9IG5wLmFycmF5KGltZGJfeV90ZXN0KQoKIyBUYWtlIG9uZSByZXZpZXcuCnByaW50KGltZGJfcmV2aWV3c190cmFpbls4N10pCgpwcmludChpbWRiX3lfdHJhaW5bODddKSAgIyBMYWJlbC4gMCBhcyBuZWdhdGl2ZSBhbmQgMSBhcyBwb3NpdGl2ZS4KYGBgCgpXZSB1c2UgdGhlIGRhdGEgcHJlcGFyZWQgYnkgYHRlbnNvcmZsb3ctZGF0YXNldHNgIGhlcmUganVzdCB0byBzYXZlIHNvbWUgdGltZS4KRm9yIHRob3NlIHdobyB3YW50IHRvIHByb2Nlc3MgdGhlIGRhdGEgaW4gaXRzIHZlcnkgb3JpZ2luYWwgZm9ybWF0ICh3aGVyZSBvbmUgcmV2aWV3IGlzIGluIG9uZSBgLnR4dGAgZmlsZSksCnRoZSBmaWxlcyBjYW4gYmUgZG93bmxvYWRlZCBieSB0aGlzIHBpZWNlIG9mIGNvZGU6CgpgYGBweXRob24KaW1kYl9yZW1vdGVfcGF0aCA9ICJodHRwczovL2FpLnN0YW5mb3JkLmVkdS9+YW1hYXMvZGF0YS9zZW50aW1lbnQvYWNsSW1kYl92MS50YXIuZ3oiCmltZGJfZm5hbWUgPSBvcy5wYXRoLmJhc2VuYW1lKGltZGJfcmVtb3RlX3BhdGgpCmltZGJfbG9jYWxfcGF0aCA9IG9zLnBhdGguam9pbihjYWNoZV9kaXIsICJkYXRhc2V0cyIsIGltZGJfZm5hbWUpCgppZiBub3Qgb3MucGF0aC5leGlzdHMoaW1kYl9sb2NhbF9wYXRoKToKICBfID0gdGYua2VyYXMudXRpbHMuZ2V0X2ZpbGUoZm5hbWU9aW1kYl9mbmFtZSwgb3JpZ2luPWltZGJfcmVtb3RlX3BhdGgsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGV4dHJhY3Q9VHJ1ZSwgY2FjaGVfZGlyPWNhY2hlX2RpcikKYGBgCgojIyMgRXhwbGFpbiBSYW5kb20gRm9yZXN0CgpMZXQncyBidWlsZCBhIHJhbmRvbSBmb3Jlc3Qgd2l0aCBURi1JREYgYXMgb3VyIGZlYXR1cmUgc3BhY2UuCldlIHdpbGwgdXNlIHRoZSBwb3B1bGFyIGBzY2lraXQtbGVhcm5gIGxpYnJhcnkgZm9yIGltcGxlbWVudGF0aW9uLgpeW0l0IHdpbGwgYmUgbXVjaCBmYXN0ZXIgaWYgd2UgY2hvb3NlIGB4Z2Jvb3N0YCdzIG9yIGBsaWdodGdibWAncyBpbXBsZW1lbnRhdGlvbiBvZiByYW5kb20gZm9yZXN0LgpIb3dldmVyLCB0byBkZW1vbnN0cmF0ZSBjb21wYXRpYmlsaXR5IG9mIGBsaW1lYCB3aXRoIGBzY2lraXQtbGVhcm5gIHdlIHB1cnBvc2VseSBjaG9vc2UgdGhlIHNsb3dlciBpbXBsZW1lbnRhdGlvbiBoZXJlLl0KCmBgYHtweXRob24gdGZpZGZ9CiMgV2UgZHJvcCB3b3JkcyB0aGF0IGFyZSB0b28gZnJlcXVlbnQgb3IgdG9vIHJhcmUgaW4gdGhlIHRyYWluaW5nIGRhdGFzZXQuCmltZGJfdmVjdG9yaXplciA9IFRmaWRmVmVjdG9yaXplcihsb3dlcmNhc2U9VHJ1ZSwgbWluX2RmPTEwLCBtYXhfZGY9LjkpCmltZGJfWF90cmFpbiA9IGltZGJfdmVjdG9yaXplci5maXRfdHJhbnNmb3JtKGltZGJfcmV2aWV3c190cmFpbikKaW1kYl9YX3Rlc3QgPSBpbWRiX3ZlY3Rvcml6ZXIudHJhbnNmb3JtKGltZGJfcmV2aWV3c190ZXN0KQpwcmludChsZW4oaW1kYl92ZWN0b3JpemVyLnZvY2FidWxhcnlfKSkgICMgV2l0aG91dCBPT1YgdG9rZW4uCmBgYAoKYGBge3B5dGhvbiBpbWRiX3JmfQppbWRiX3JmX21vZGVsX2ZpbGUgPSBvcy5wYXRoLmpvaW4obW9kZWxfZGlyLCAidGV4dF9yZi5qb2JsaWIiKQoKIyBTYXZlL3JlbG9hZCB0aGUgbW9kZWwgdG8gc2F2ZSBub3RlYm9vayByZW5kZXJpbmcgdGltZS4KaWYgb3MucGF0aC5leGlzdHMoaW1kYl9yZl9tb2RlbF9maWxlKToKICBpbWRiX3JmID0gam9ibGliLmxvYWQoaW1kYl9yZl9tb2RlbF9maWxlKQplbHNlOgogIGltZGJfcmYgPSBSYW5kb21Gb3Jlc3RDbGFzc2lmaWVyKG5fZXN0aW1hdG9ycz0zMDAsIHJhbmRvbV9zdGF0ZT02NCwgbl9qb2JzPS0yKQogIF8gPSBpbWRiX3JmLmZpdChpbWRiX1hfdHJhaW4sIGltZGJfeV90cmFpbikKICBfID0gam9ibGliLmR1bXAoaW1kYl9yZiwgaW1kYl9yZl9tb2RlbF9maWxlKQoKaW1kYl9yZl9wcmVkID0gaW1kYl9yZi5wcmVkaWN0KGltZGJfWF90ZXN0KQppbWRiX3JmX3loYXQgPSBpbWRiX3JmLnByZWRpY3RfcHJvYmEoaW1kYl9YX3Rlc3QpWzosMV0KCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydChpbWRiX3lfdGVzdCwgaW1kYl9yZl9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZShpbWRiX3lfdGVzdCwgaW1kYl9yZl95aGF0KSkKYGBgCgpBcyBhIGJhc2VsaW5lIHdpdGhvdXQgZXh0ZW5zaXZlIHR1bmluZyAod2UgZGlkbid0IHR1bmUgYW55dGhpbmcgaW5kZWVkISksCnJhbmRvbSBmb3Jlc3Qgc2VlbXMgdG8gcGVyZm9ybSBmYWlybHkgd2VsbCBvbiB0aGlzIGRhdGFzZXQuCgpBcyBwYXJ0IG9mIHRoZSBhbGdvcml0aG0ncyBkZXNpZ24gd2UgYXJlIGFibGUgdG8gZGVyaXZlIGEgZ2xvYmFsIHZpZXcgb2YgZmVhdHVyZSBpbXBvcnRhbmNlLgpUaGlzIGlzIGJhc2VkIG9uIGhvdyBtdWNoIGVhY2ggZmVhdHVyZSBjYW4gcmVkdWNlIHRoZSBpbXB1cml0eSBkdXJpbmcgYWxsIHRyZWUgc3BsaXR0aW5ncy4KRm9yIGV4YW1wbGUsCndlIGNhbiBwbG90IHRoZSB0b3AgMjAgZmVhdHVyZXM6CgpgYGB7cHl0aG9uIGltZGJfcmZfZmVhdF9pbXB9CnNvcnRlZF92b2NhYiA9IHNvcnRlZChpbWRiX3ZlY3Rvcml6ZXIudm9jYWJ1bGFyeV8uaXRlbXMoKSwga2V5PWxhbWJkYSBrdjoga3ZbMV0pCnNvcnRlZF92b2NhYiA9IFt3IGZvciB3LCBpIGluIHNvcnRlZF92b2NhYl0KCmltZGJfcmZfZmVhdF9pbXAgPSBwZC5TZXJpZXMoaW1kYl9yZi5mZWF0dXJlX2ltcG9ydGFuY2VzXywgaW5kZXg9c29ydGVkX3ZvY2FiKS5zb3J0X3ZhbHVlcygpCmF4ID0gaW1kYl9yZl9mZWF0X2ltcC50YWlsKDIwKS5wbG90KGtpbmQ9ImJhcmgiKQpwbHQuc2hvdygpCmBgYAoKQXMgb25lIGNhbiBzZWUsCmNvbW1vbiBhZGplY3RpdmVzIGRlc2NyaWJpbmcgZ29vZCBvciBiYWQgdGhpbmdzIGdlbmVyYWxseSBoYXZlIGxhcmdlciBpbXBhY3QgaW4gdGhlIG1vZGVsLAp3aGljaCBpcyB0b3RhbGx5IGV4cGVjdGVkLgpCdXQgd2UgYWxzbyBzZWUgaW5mbHVlbnRpYWwgd29yZHMgc3VjaCBhcyBganVzdGAgYW5kIGBtaW51dGVzYCB3aGljaCBhcmUgcXVpdGUgbmV1dHJhbCBhbmQgY29udGFpbiBubyB1c2VmdWwgaW5mb3JtYXRpb24gb24gdGhlaXIgb3duLgpUaGV5IG1heSBiZSAqam9pbnRseSogaW1wb3J0YW50IGluIHRoZSBtb2RlbCBzaW5jZSBhIHRyZWUgbW9kZWwgYWxsb3dzIGludGVyYWN0aW9uIGJldHdlZW4gdmFyaWFibGVzLgpCdXQgd2Ugd29uJ3QgYmUgYWJsZSB0byBnbyBkZWVwZXIgYmV5b25kIHRoZSB1bmNvbmRpdGlvbmFsIHZpZXcgd2UgZGVyaXZlZCBhcyBhIGdsb2JhbCBmZWF0dXJlIHJhbmtpbmcuCgpJbnRlcnByZXRhdGlvbiBvZiB0aGUgaW1wdXJpdHktYmFzZWQgcmFua2luZyBtdXN0IGJlIHZlcnkgY2FyZWZ1bC4KRm9yIGV4YW1wbGUsCnJlbGF0ZWQgZmVhdHVyZXMgd2lsbCB0aGVvcmV0aWNhbGx5IGhhdmUgc2ltaWxhciBpbXBhY3QgYnV0IG9ubHkgb25lIG9mIGl0IHdpbGwgZ2FpbiBoaWdoZXIgc2NvcmUgKGFuZCBzdXBwcmVzcyB0aGUgb3RoZXIpIGluIHRoZSByYW5raW5nLgpXaGljaCBvbmUgc3RhbmRzIG91dCBpcyB0b3RhbGx5IHJhbmRvbSBkdWUgdG8gdGhlIHdheSB0cmVlIHNwbGl0dGluZyBpcyBwZXJmb3JtZWQgZHVyaW5nIHRyYWluaW5nLgoKSW4gZ2VuZXJhbCBpdCBpcyBOT1QgcmVjb21tZW5kZWQgdG8gdXNlIGltcHVyaXR5IG9yIGxvc3MtYmFzZWQgZmVhdHVyZSByYW5raW5nIHRvICppbnRlcnByZXQqIGEgdHJlZSBlbnNlbWJsZSBtb2RlbC4KU3VjaCByYW5raW5nIGluZm9ybWF0aW9uIGlzIHN0aWxsIHVzZWZ1bCB0byB1bmRlcnN0YW5kIGRpZmZlcmVudCBhc3BlY3RzIG9mIHRoZSBtb2RlbCwKYW5kIGNhbiBiZSB1c2VkIHRvIHN1YnNldCBmZWF0dXJlIHRvIGNvdW50ZXIgb3Zlci1maXR0aW5nIGlzc3VlLCBpZiBhbnkuCkJ1dCBpdCB3b24ndCBoZWxwIHJlYWxseSBleHBsYWluIHRoZSBtb2RlbCBhdCB0aGUgcHJlZGljdGlvbi1sZXZlbDogKldoeSBpcyBteSBtb2RlbCBtYWtpbmcgc3VjaCBwcmVkaWN0aW9uPyoKQW5kIHRoaXMgaXMgZXhhY3RseSB3aHkgd2UgbmVlZCBhIGV4cGxhbmF0aW9uIG1vZGVsIGluIHRoZSBmaXJzdCBwbGFjZS4KCk5vdyBtb3ZlIG9uIHRvIG1vZGVsIGV4cGxhbmF0aW9uIHdpdGggTElNRS4KV2UgcGljayB1cCBvbmUgdHJ1ZSBwb3NpdGl2ZSBhbmQgb25lIGZhbHNlIHBvc2l0aXZlIGNhc2UgbWFkZSBieSBvdXIgcmFuZG9tIGZvcmVzdCBtb2RlbCB0byBzZWUgaG93IHRoZSBleHBsYW5hdGlvbiBtb2RlbCB3aWxsIGV4cGxhaW4gZWFjaCBjYXNlLgoKYGBge3B5dGhvbiBsaW1lX2ltZGJfcmZ9CmZyb20gbGltZS5saW1lX3RleHQgaW1wb3J0IExpbWVUZXh0RXhwbGFpbmVyCgojIFdlIG5lZWQgYSBwaXBlbGluZSBzaW5jZSBMaW1lVGV4dEV4cGxhaW5lci5leHBsYWluX2luc3RhbmNlIGV4cGVjdHMgcmF3IHRleHQgaW5wdXQuCmltZGJfcmZfcGlwZSA9IG1ha2VfcGlwZWxpbmUoaW1kYl92ZWN0b3JpemVyLCBpbWRiX3JmKQppbWRiX3JmX2V4cGxhaW5lciA9IExpbWVUZXh0RXhwbGFpbmVyKGNsYXNzX25hbWVzPVsiTmVnYXRpdmUiLCAiUG9zaXRpdmUiXSkKCmltZGJfcmZfdHBfaWR4ID0gbnAud2hlcmUobnAubG9naWNhbF9hbmQoaW1kYl9yZl9wcmVkID09IDEsIGltZGJfeV90ZXN0ID09IDEpKVswXQppbWRiX3JmX2ZwX2lkeCA9IG5wLndoZXJlKG5wLmxvZ2ljYWxfYW5kKGltZGJfcmZfcHJlZCA9PSAxLCBpbWRiX3lfdGVzdCA9PSAwKSlbMF0KCiMgV2UgdGFrZSBvbmUgdHJ1ZSBwb3NpdGl2ZSBhbmQgb25lIGZhbHNlIHBvc2l0aXZlIGV4YW1wbGUgdG8gZGVtbyBleHBsYW5hdGlvbi4KaW1kYl9yZl90cF9leHAgPSBpbWRiX3JmX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIGltZGJfcmV2aWV3c190ZXN0W2ltZGJfcmZfdHBfaWR4WzBdXSwgaW1kYl9yZl9waXBlLnByZWRpY3RfcHJvYmEsIG51bV9mZWF0dXJlcz02KQppbWRiX3JmX2ZwX2V4cCA9IGltZGJfcmZfZXhwbGFpbmVyLmV4cGxhaW5faW5zdGFuY2UoCiAgaW1kYl9yZXZpZXdzX3Rlc3RbaW1kYl9yZl9mcF9pZHhbMF1dLCBpbWRiX3JmX3BpcGUucHJlZGljdF9wcm9iYSwgbnVtX2ZlYXR1cmVzPTYpCiMgRm9yIGlweW5iLCBvbmUgY2FuIHNpbXBseSBjYWxsIGltZGJfdHBfZXhwLnNob3dfaW5fbm90ZWJvb2sodGV4dD1UcnVlKSB0byBlbWJlZCB0aGUgaHRtbCBvdXRwdXQuCgppbWRiX3JmX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X3JmX3RwLmh0bWwiKQppbWRiX3JmX2ZwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X3JmX2ZwLmh0bWwiKQpgYGAKCiMjIyMgQSBUcnVlIFBvc2l0aXZlIFByZWRpY3Rpb24gRXhwbGFpbmVkIHstfQoKYGBge3IsIGVjaG89RkFMU0V9CmlmICggIWZpbGUuZXhpc3RzKCJsaW1lLmpzIikgKSB7CiAgd3JpdGVfbGltZV9qcygiL3RtcC9leHBsYWluX3RleHRfcmZfdHAuaHRtbCIpCn0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGV4dF9yZl90cC5odG1sIikpCmBgYAoKPGJyPgoKT3VyIFJGIG1vZGVsIGRvZXNuJ3Qgc2VlbSB0byBiZSB2ZXJ5IGNvbmZpZGVudCBvbiB0aGlzIHBhcnRpY3VsYXIgcG9zaXRpdmUgZXhhbXBsZSBpbmRlZWQuClRoZXJlIGlzIG5vIGRvbWluYW50IHNpbmdsZSB3b3JkIGNhbiBkcml2ZSB0aGUgcHJlZGljdGlvbiBpbiB0aGUgY29ycmVjdCBkaXJlY3Rpb24uClRoZSBjb250cmlidXRpbmcgd29yZHMgYXJlIGFsc28gbW9zdGx5IG5ldXRyYWwgb24gdGhlaXIgb3duLgpXZSBjYW4gY29uZmlybSB0aGF0IHRoZSByZXN1bHQgb2YgdGhpcyBwcmVkaWN0aW9uIHdpbGwgYmUgdmVyeSBzZW5zaXRpdmUgYW5kIG5vdCByb2J1c3QuCkFkbWl0dGVkbHkgdGhpcyByZXZpZXcgZG9lcyBzaG93IHNvbWUgbWl4dHVyZXMgb2YgcG9zaXRpdmUgYW5kIG5lZ2F0aXZlIHZpZXdzLgoKIyMjIyBBIEZhbHNlIFBvc2l0aXZlIFByZWRpY3Rpb24gRXhwbGFpbmVkIHstfQoKTm93IGxldCdzIGxvb2sgYXQgYSBmYWxzZSBwb3NpdGl2ZSBleGFtcGxlLAp3aGVyZSBvdXIgUkYgbW9kZWwgd3JvbmdseSBsYWJlbGVkIGFzIGEgcG9zaXRpdmUgcmV2aWV3LgoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RleHRfcmZfZnAuaHRtbCIpKQpgYGAKCjxicj4KCkluIHRoaXMgZXhhbXBsZSBhIHNpbmdsZSBwb3NpdGl2ZSB3b3JkIGBncmVhdGAgKHdyb25nbHkpIGRvbWluYXRlIHRoZSBwcmVkaWN0aW9uIHRvd2FyZCBhIHBvc2l0aXZlIHNlbnRpbWVudC4KQW5kIHdlIHJlYWxpemUgdGhlIG1vZGVsIGRpZG4ndCByZXNwb25zZSB3ZWxsIHRvIHNvbWUgbmVnYXRpdmUgc2lnbmFscywKZXNwZWNpYWxseSBmb3IgdGhlIHdvcmQgYGJvcmVgLgoKSWYgd2UgZXhhbWluZSBtb3JlIGNhc2VzIHdlIG1heSBoYXZlIG1vcmUgY2x1ZXMgb24gaG93IHRoZSBtb2RlbCBtaXMtYmVoYXZlcywKYW5kIHdlIGNhbiBjb21lIHVwIHdpdGggYSBzdHJhdGVneSBhY2NvcmRpbmdseSB0byBpbXByb3ZlIGl0LgpGb3Igbm93IHdlJ2xsIHN0b3AgaGVyZSBhbmQgdHJ5IGV4cGVyaW1lbnRpbmcgd2l0aCBvdGhlciBsZWFybmluZyBhbGdvcml0aG1zIGhlcmVhZmVyLgoKIyMjIEV4cGxhaW4gTmV1cmFsIE5ldHdvcmtzCgpOb3cgbGV0J3MgdHJ5IGEgc2hhbGxvdyBuZXVyYWwgbmV0d29yayBtb2RlbCB3aXRoIHdvcmQgZW1iZWRkaW5ncyB0cmFpbmVkIGZyb20gc2NyYXRjaC4KV2UgdXNlIGB0ZW5zb3JmbG93LmtlcmFzYCBBUEkgdG8gcXVpY2tseSBidWlsZCBhbmQgdHJhaW4gYSBuZXVyYWwgbmV0LgpXZSBhdmVyYWdlIHdvcmQgZW1iZWRkaW5ncyBhcyB0aGUgZG9jdW1lbnQgZW1iZWRkaW5ncyBmb3IgZWFjaCByZXZpZXcsCnRoZW4gZmVlZC1mb3J3YXJkIGEgUmVMVSBsYXllciBiZWZvcmUgdGhlIHNpZ21vaWQgYWN0aXZhdGlvbiBmb3IgY3Jvc3MtZW50cm9weSBvcHRpbWl6YXRpb24uCgpBcyBhbiBleGVyY2lzZSwKaW5zdGVhZCBvZiByZS11c2luZyB0aGUgdm9jYWJ1bGFyeSBidWlsdCBieSBgVGZpZGZWZWN0b3JpemVyYCB3aXRoIGBzY2lraXQtbGVhcm5gLAp3ZSB3aWxsIHJlLXRva2VuaXplIHRoZSB0ZXh0IGRhdGEgd2l0aCBga2VyYXMucHJlcHJvY2Vzc2luZ2AgbW9kdWxlLgpUaGUgaW5oZXJlbnQgY29uc2lzdGVuY3kgdW5kZXIgdGhlIEtlcmFzIGZyYW1ld29yayB3aWxsIGFsc28gc2ltcGxpZnkgb3VyIGxhdHRlciB3b3JrcyBvbiBuZXR3b3JrIGxheWVyaW5nLgoKYGBge3B5dGhvbiBpbWRiX25ufQpmcm9tIHRlbnNvcmZsb3cua2VyYXMucHJlcHJvY2Vzc2luZy50ZXh0IGltcG9ydCBUb2tlbml6ZXIKZnJvbSB0ZW5zb3JmbG93LmtlcmFzLnByZXByb2Nlc3Npbmcuc2VxdWVuY2UgaW1wb3J0IHBhZF9zZXF1ZW5jZXMKCiMgQnVpbGQgdm9jYWJ1bGFyeS4gV2UgdXNlIHNpbWlsYXIgc2l6ZSBhcyBpbiBvdXIgcHJldmlvdXMgVGZpZGZWZWN0b3JpemVyLgojIFNpbmNlIHdlIHdpbGwgdXNlIHplcm8gcGFkZGluZywgMCBjYW5ub3QgYmUgdXNlZCBhcyBPT1YgaW5kZXguCiMgS2VyYXMgdG9rZW5pemVyIGJ5IGRlZmF1bHQgcmVzZXJ2ZXMgMCBhbHJlYWR5LiBPT1YgdG9rZW4sIGlmIHVzZWQsIHdpbGwgYmUgaW5kZXhlZCBhdCAxLgojIE5vdGUgdGhhdCBsZW4odG9rZW5pemVyLmluZGV4X3dvcmQpIHdpbGwgYmUgYWxsIHZvY2FidWxhcnkgaW5zdGVhZCBvZiBgbnVtX3dvcmRzYC4Kdm9jYWJfc2l6ZSA9IDIwMDAxICAjICsxIGZvciAwIGluZGV4IHVzZWQgZm9yIHBhZGRpbmcuCm9vdl90b2tlbiA9ICI8dW5rPiIKdG9rZW5pemVyID0gVG9rZW5pemVyKGxvd2VyPVRydWUsIG9vdl90b2tlbj1vb3ZfdG9rZW4sIG51bV93b3Jkcz12b2NhYl9zaXplKQp0b2tlbml6ZXIuZml0X29uX3RleHRzKGltZGJfcmV2aWV3c190cmFpbikKCiMgRW5jb2RlIHRleHQgd2l0aCBwYWRkaW5nIHRvIGVuc3VyZSBmaXhlZC1sZW5ndGggaW5wdXQuCnNlcV90cmFpbiA9IHRva2VuaXplci50ZXh0c190b19zZXF1ZW5jZXMoaW1kYl9yZXZpZXdzX3RyYWluKQpzZXFfdHJhaW5fcGFkZGVkID0gcGFkX3NlcXVlbmNlcyhzZXFfdHJhaW4sIHBhZGRpbmc9InBvc3QiKQptYXhsZW4gPSBzZXFfdHJhaW5fcGFkZGVkLnNoYXBlWzFdCnNlcV90ZXN0ID0gdG9rZW5pemVyLnRleHRzX3RvX3NlcXVlbmNlcyhpbWRiX3Jldmlld3NfdGVzdCkKc2VxX3Rlc3RfcGFkZGVkID0gcGFkX3NlcXVlbmNlcyhzZXFfdGVzdCwgcGFkZGluZz0icG9zdCIsIG1heGxlbj1tYXhsZW4pCgphc3NlcnQgdG9rZW5pemVyLmluZGV4X3dvcmRbMV0gPT0gb292X3Rva2VuCmFzc2VydCBzZXFfdHJhaW5fcGFkZGVkLm1heCgpID09IHZvY2FiX3NpemUgLSAxCgojIFdyYXAgS2VyYXMgU2VxdWVudGlhbCBtb2RlbCB3aXRoIHNjaWtpdC1sZWFybiBBUEkuCiMgVGhpcyBpcyBiZWNhdXNlIExpbWVUZXh0RXhwbGFpbmVyIHNlZW1zIGJ1Z2d5IHdpdGggYSBuYXRpdmUgS2VyYXMgbW9kZWwuCm5uX21vZGVsX2ZpbGUgPSBvcy5wYXRoLmpvaW4obW9kZWxfZGlyLCAidGV4dF9jbGZfbm4uaDUiKQoKZGVmIG5uX21vZGVsX2ZuKCk6CiAgZW1iZWRkaW5nX3NpemUgPSA2NAogIG1vZGVsID0gdGYua2VyYXMuU2VxdWVudGlhbChbCiAgICB0Zi5rZXJhcy5sYXllcnMuRW1iZWRkaW5nKAogICAgICB2b2NhYl9zaXplLCBlbWJlZGRpbmdfc2l6ZSwgaW5wdXRfbGVuZ3RoPW1heGxlbiwKICAgICAgbWFza196ZXJvPVRydWUsIG5hbWU9IndvcmRfZW1iZWRkaW5nIiksCiAgICB0Zi5rZXJhcy5sYXllcnMuR2xvYmFsQXZlcmFnZVBvb2xpbmcxRChuYW1lPSJkb2NfZW1iZWRkaW5nIiksCiAgICB0Zi5rZXJhcy5sYXllcnMuRGVuc2UoZW1iZWRkaW5nX3NpemUgLyAyLCBhY3RpdmF0aW9uPSJyZWx1IiwgbmFtZT0icmVsdSIpLAogICAgdGYua2VyYXMubGF5ZXJzLkRlbnNlKDEsIGFjdGl2YXRpb249InNpZ21vaWQiLCBuYW1lPSJzaWdtb2lkIikKICBdLCBuYW1lPSJubl9jbGFzc2lmaWVyIikKICBtb2RlbC5jb21waWxlKG9wdGltaXplcj0iYWRhbSIsCiAgICAgICAgICAgICAgICBsb3NzPSJiaW5hcnlfY3Jvc3NlbnRyb3B5IiwKICAgICAgICAgICAgICAgIG1ldHJpY3M9WyJhY2N1cmFjeSJdKQogIHJldHVybiBtb2RlbAoKcHJpbnQobm5fbW9kZWxfZm4oKS5zdW1tYXJ5KGxpbmVfbGVuZ3RoPTkwKSkKCmltZGJfbm4gPSB0Zi5rZXJhcy53cmFwcGVycy5zY2lraXRfbGVhcm4uS2VyYXNDbGFzc2lmaWVyKG5uX21vZGVsX2ZuKQppZiBvcy5wYXRoLmV4aXN0cyhubl9tb2RlbF9maWxlKToKICAjIFJlc3RvcmUgdGhlIG1vZGVsIHdpdGggd3JhcHBlci4KICBpbWRiX25uLm1vZGVsID0gdGYua2VyYXMubW9kZWxzLmxvYWRfbW9kZWwobm5fbW9kZWxfZmlsZSkKICBpbWRiX25uLmNsYXNzZXNfID0gbnAuYXJyYXkoWzAsIDFdKQplbHNlOgogIG1ldHJpY3MgPSBpbWRiX25uLmZpdCgKICAgIHg9c2VxX3RyYWluX3BhZGRlZCwgeT1pbWRiX3lfdHJhaW4sCiAgICBiYXRjaF9zaXplPTI1NiwgZXBvY2hzPTEwLAogICAgdmFsaWRhdGlvbl9kYXRhPShzZXFfdGVzdF9wYWRkZWQsIGltZGJfeV90ZXN0KSwKICAgIHZhbGlkYXRpb25fc3RlcHM9MjAsCiAgICBjYWxsYmFja3M9WwogICAgICB0Zi5rZXJhcy5jYWxsYmFja3MuRWFybHlTdG9wcGluZyhtb25pdG9yPSJ2YWxfbG9zcyIsIHBhdGllbmNlPTIpLAogICAgICB0Zi5rZXJhcy5jYWxsYmFja3MuTW9kZWxDaGVja3BvaW50KG5uX21vZGVsX2ZpbGUsIG1vbml0b3I9InZhbF9sb3NzIiwgc2F2ZV9iZXN0X29ubHk9VHJ1ZSkKICAgIF0sCiAgICB2ZXJib3NlPTIpCgppbWRiX25uX3loYXQgPSBpbWRiX25uLnByZWRpY3RfcHJvYmEoc2VxX3Rlc3RfcGFkZGVkKVs6LDFdCmltZGJfbm5fcHJlZCA9IChpbWRiX25uX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydChpbWRiX3lfdGVzdCwgaW1kYl9ubl9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZShpbWRiX3lfdGVzdCwgaW1kYl9ubl95aGF0KSkKYGBgCgpCYXNlZCBvbiB0aGUgdGVzdGluZyBBVUMgc2NvcmUsCm91ciBzaGFsbG93IG5ldXJhbCBuZXR3b3JrIG1vZGVsIGRpZCBvdXRwZXJmb3JtIGEgcmFuZG9tIGZvcmVzdC4KTGV0J3Mgc2VlIGhvdyB0aGUgZXhwbGFuYXRpb24gbW9kZWwgdGVsbCB1cyBhYm91dCB0aGUgYmVoYXZpb3Igb2YgdGhlIG5ldXJhbCBuZXR3b3JrIG1vZGVsLgoKYGBge3B5dGhvbiBsaW1lX2ltZGJfbm59CmRlZiBubl9wcmVkaWN0X2ZuKHRleHQpOgogICMgVGhpcyBpcyBmb3Igc2tsZWFybiB3cmFwcGVyIG9ubHkuCiAgc2VxID0gdG9rZW5pemVyLnRleHRzX3RvX3NlcXVlbmNlcyh0ZXh0KQogIHNlcSA9IHBhZF9zZXF1ZW5jZXMoc2VxLCBwYWRkaW5nPSJwb3N0IiwgbWF4bGVuPW1heGxlbikKICByZXR1cm4gaW1kYl9ubi5wcmVkaWN0X3Byb2JhKHNlcSkKCmltZGJfbm5fZXhwbGFpbmVyID0gTGltZVRleHRFeHBsYWluZXIoY2xhc3NfbmFtZXM9WyJOZWdhdGl2ZSIsICJQb3NpdGl2ZSJdKQoKIyBFeHBsYWluIHRoZSBzYW1lIGV4YW1wbGVzIGFzIGluIFJGLgppbWRiX25uX3RwX2V4cCA9IGltZGJfbm5fZXhwbGFpbmVyLmV4cGxhaW5faW5zdGFuY2UoCiAgaW1kYl9yZXZpZXdzX3Rlc3RbaW1kYl9yZl90cF9pZHhbMF1dLCBubl9wcmVkaWN0X2ZuLCBudW1fZmVhdHVyZXM9NikKaW1kYl9ubl9mcF9leHAgPSBpbWRiX25uX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIGltZGJfcmV2aWV3c190ZXN0W2ltZGJfcmZfZnBfaWR4WzBdXSwgbm5fcHJlZGljdF9mbiwgbnVtX2ZlYXR1cmVzPTYpCgppbWRiX25uX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X25uX3RwLmh0bWwiKQppbWRiX25uX2ZwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X25uX2ZwLmh0bWwiKQpgYGAKCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKHBhcnNlX2xpbWVfaHRtbF9vdXRwdXQoIi90bXAvZXhwbGFpbl90ZXh0X25uX3RwLmh0bWwiKSkKYGBgCgo8YnI+CgpUaGUgYWJvdmUgaXMgdGhlIExJTUUgZXhwbGFuYXRpb24gb2YgdGhlIHNhbWUgcG9zaXRpdmUgZXhhbXBsZSBwcmV2aW91c2x5IGV4cGxhaW5lZCB3aXRoIGEgUkYgbW9kZWwuCldlIHJlYWxpemUgdGhhdCwKdGhvdWdoIGJvdGggbW9kZWxzIGV2ZW50dWFsbHkgZ2l2ZSBhIHBvc2l0aXZlIHByZWRpY3Rpb24sCnRoZSBuZXVyYWwgbmV0d29yayBtb2RlbCBoYXMgYSB2ZXJ5IGRpZmZlcmVudCBvcGluaW9uIG9uIGhvdyB0aGUgcG9zaXRpdmUgcHJlZGljdGlvbiBpcyBmb3JtdWxhdGVkLgpJbnN0ZWFkIG9mIGJlaW5nIGNvbmZ1c2VkIGFuZCBpbmRlY2lzaXZlLAp0aGUgTk4gbW9kZWwgaXMgYWN0dWFsbHkgb3Zlci1jb25maWRlbnQgYWJvdXQgdGhpcyBwcmVkaWN0aW9uIQpTb21lIG5ldXRyYWwgd29yZHMgaGF2ZSBkaXNwcm9wb3J0aW9uYXRlIGNvbnRyaWJpdGlvbiB0byB0aGUgcG9zaXRpdmUsCnBvaW50aW5nIG91dCB0aGUgcG90ZW50aWFsIGRpcmVjdGlvbiB0byBpbXByb3ZlIHRoZSBtb2RlbC4KRm9yIGV4YW1wbGUsCmNhbiBhIGJpZ3JhbSB0b2tlbml6ZXIgYmUgYmV0dGVyPwoKSG93IGFib3V0IHRoZSBzZWNvbmQgZXhhbXBsZSAod2hpY2ggaXMgYSBuZWdhdGl2ZSByZXZpZXcpPwpPdXIgTk4gbW9kZWwgYWxzbyBtYWtlcyBhIG1pc3Rha2Ugb24gdGhpcyBuZWdhdGl2ZSByZXZpZXcsCmJ5IHByZWRpY3RpbmcgaXQgYXMgYSBwb3NpdGl2ZSBvbmUuCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGV4dF9ubl9mcC5odG1sIikpCmBgYAoKPGJyPgoKV2hhdCdzIGRpZmZlcmVudCBoZXJlIGlzIHRoZSByZWFjdGlvbiB0byB0aGUgbmVnYXRpdmUgd29yZCBgYm9yZWAsCndoaWNoIGlzIG5vdCBzZWVuIGluIFJGLgoKV2l0aG91dCBhIGV4cGxhbmF0aW9uIG1vZGVsLAppdCB3b24ndCBiZSBlYXN5IGZvciB1cyB0byBjb21wYXJlIHR3byBtb2RlbHMgYXQgdGhpcyBsZXZlbCBvZiBkZXRhaWxzLgoKIyMjIEV4cGxhaW4gVHJhbnNmZXIgTGVhcm5pbmcKCk9uZSBzdGVwIGZ1cnRoZXIsCmxldCdzIHVzZSBwcmUtdHJhaW5lZCB3b3JkIGVtYmVkZGluZ3MgZm9yIHRoZSBuZXVyYWwgbmV0cyBhbmQgYnVpbGQgYW5vdGhlciBleHBsYW5hdGlvbiBtb2RlbC4KV2Ugd2lsbCB1c2UgW0dsb1ZlXShodHRwczovL25scC5zdGFuZm9yZC5lZHUvcHJvamVjdHMvZ2xvdmUvKSAoQHBlbm5pbmd0b24yMDE0Z2xvdmUpLgpXZSB1c2UganVzdCB0aGUgc21hbGxlciBHbG9WZSBtb2RlbCBzaW5jZSBvdXIgZGF0YXNldCBpcyBxdWl0ZSBzbWFsbC4KCmBgYHtweXRob24gbWF5YmVfZG93bmxvYWRfZ2xvdmUsIHJlc3VsdHM9ImhpZGUifQojIERvd25sb2FkIEdsb1ZlIHByZS10cmFpbmVkIGVtYmVkZGluZ3MuCiMgVGhlIGZpbGUgaXMgYWJvdXQgODAwTUIgc28gbWF5IHRha2Ugc29tZSB0aW1lLgpnbG92ZTZiX3JlbW90ZV9wYXRoID0gImh0dHA6Ly9ubHAuc3RhbmZvcmQuZWR1L2RhdGEvZ2xvdmUuNkIuemlwIgpnbG92ZTZiX2xvY2FsX3BhdGggPSBvcy5wYXRoLmpvaW4oY2FjaGVfZGlyLCAiZGF0YXNldHMiLCAiZ2xvdmUuNkIuNTBkLnR4dCIpCmdsb3ZlNmJfZm5hbWUgPSBvcy5wYXRoLmJhc2VuYW1lKGdsb3ZlNmJfcmVtb3RlX3BhdGgpCmlmIG5vdCBvcy5wYXRoLmV4aXN0cyhnbG92ZTZiX2xvY2FsX3BhdGgpOgogIF8gPSB0Zi5rZXJhcy51dGlscy5nZXRfZmlsZShmbmFtZT1nbG92ZTZiX2ZuYW1lLCBvcmlnaW49Z2xvdmU2Yl9yZW1vdGVfcGF0aCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXh0cmFjdD1UcnVlLCBjYWNoZV9kaXI9Y2FjaGVfZGlyKQoKZ2xvdmVfYWxsID0gcGQucmVhZF9jc3YoZ2xvdmU2Yl9sb2NhbF9wYXRoLCBzZXA9IiAiLCBoZWFkZXI9Tm9uZSwgaW5kZXhfY29sPTAsIHF1b3Rpbmc9MykKYGBgCgpJbiBidWlsZGluZyB0aGUgR2xvVmUgZW1iZWRkaW5ncyB3ZSBuZWVkIHRvIHRha2Ugc3BlY2lhbCBjYXJlIGFib3V0IG91dC1vZi12b2NhYnVsYXJ5IHRva2VuIEFORCBwYWRkaW5nIGluZGV4IHNpbmNlIHdlIHdpbGwgYmUgdXNpbmcgdGhlIEtlcmFzIEFQSS4KCmBgYHtweXRob24gaW1kYl90cmFuc2Zlcl9sZWFybmluZ192b2NhYn0KIyBNYXAgdm9jYWJ1bGFyeSB0byBwcmUtdHJhaW5lZCBlbWJlZGRpbmdzLgptYXRjaGVkX3Rva3MgPSBbXQpmb3IgaSwgdyBpbiB0b2tlbml6ZXIuaW5kZXhfd29yZC5pdGVtcygpOgogIGlmIGkgPCB2b2NhYl9zaXplOgogICAgaWYgdyBpbiBnbG92ZV9hbGwuaW5kZXg6CiAgICAgIG1hdGNoZWRfdG9rcy5hcHBlbmQodykKICAgIGVsc2U6CiAgICAgIG1hdGNoZWRfdG9rcy5hcHBlbmQob292X3Rva2VuKQoKIyBOb3RlIHRoYXQgR2xvVmUgcHJlLXRyYWluZWQgZW1iZWRkaW5ncyBkb2VzIG5vdCBpbmNsdWRlIGl0cyBvd24gT09WIHRva2VuLgojIFdlIHdpbGwgdXNlIGEgZ2xvYmFsIGF2ZXJhZ2UgZW1iZWRkaW5nIHRvIHJlcHJlc2VudCBPT1YgdG9rZW4uCnByaW50KGxlbihbdCBmb3IgdCBpbiBtYXRjaGVkX3Rva3MgaWYgdCA9PSBvb3ZfdG9rZW5dKSkgICMgSG93IG1hbnkgT09Wcz8KCmdsb3ZlX2FsbC5sb2Nbb292X3Rva2VuXSA9IGdsb3ZlX2FsbC52YWx1ZXMubWVhbihheGlzPTApCmdsb3ZlID0gZ2xvdmVfYWxsLmxvY1ttYXRjaGVkX3Rva3NdLnZhbHVlcwoKIyBBcHBlbmQgZHVtbXkgMC1pbmRleCB2ZWN0b3IgdG8gc3VwcG9ydCBwYWRkaW5nLgpnbG92ZSA9IG5wLnZzdGFjayhbbnAuemVyb3MoKDEsIGdsb3ZlLnNoYXBlWzFdKSksIGdsb3ZlXSkKcHJpbnQoZ2xvdmUuc2hhcGUpCmBgYAoKTm93IGxldCdzIGJ1aWxkIHRoZSBuZXVyYWwgbmV0d29yay4KTW9zdCBvZiB0aGUgY29kZSB3aWxsIGJlIHRoZSBzYW1lIGFzIGJlZm9yZSwKb25seSB0aGUgYEVtYmVkZGluZ2AgbGF5ZXIgbm93IHdlIHdpbGwgdXNlIGEgY29uc3RhbnQgbWF0cml4IGZvciBpbml0aWFsaXphdGlvbi4KV2UgbWFrZSB0aGUgR2xvVmUgZW1iZWRkaW5ncyAqdHJhaW5hYmxlKiBzbyBpdCB3aWxsIGZ1cnRoZXIgYWRhcHQgdG8gb3VyIHNwZWNpZmljIGRhdGFzZXQuCgpgYGB7cHl0aG9uIGltZGJfdHJhbnNmZXJfbGVhcm5pbmd9CnRyX21vZGVsX2ZpbGUgPSBvcy5wYXRoLmpvaW4obW9kZWxfZGlyLCAidGV4dF9jbGZfdHIuaDUiKQoKZGVmIHRyX21vZGVsX2ZuKCk6CiAgZW1iZWRkaW5nX3NpemUgPSBnbG92ZS5zaGFwZVsxXQogIG1vZGVsID0gdGYua2VyYXMuU2VxdWVudGlhbChbCiAgICB0Zi5rZXJhcy5sYXllcnMuRW1iZWRkaW5nKAogICAgICB2b2NhYl9zaXplLCBlbWJlZGRpbmdfc2l6ZSwgaW5wdXRfbGVuZ3RoPW1heGxlbiwKICAgICAgZW1iZWRkaW5nc19pbml0aWFsaXplcj10Zi5rZXJhcy5pbml0aWFsaXplcnMuQ29uc3RhbnQoZ2xvdmUpLAogICAgICB0cmFpbmFibGU9VHJ1ZSwgbWFza196ZXJvPVRydWUsIG5hbWU9Imdsb3ZlX2VtYmVkZGluZyIpLAogICAgdGYua2VyYXMubGF5ZXJzLkdsb2JhbEF2ZXJhZ2VQb29saW5nMUQobmFtZT0iZG9jX2VtYmVkZGluZyIpLAogICAgdGYua2VyYXMubGF5ZXJzLkRlbnNlKGVtYmVkZGluZ19zaXplIC8gMiwgYWN0aXZhdGlvbj0icmVsdSIsIG5hbWU9InJlbHUiKSwKICAgIHRmLmtlcmFzLmxheWVycy5EZW5zZSgxLCBhY3RpdmF0aW9uPSJzaWdtb2lkIiwgbmFtZT0ic2lnbW9pZCIpCiAgXSwgbmFtZT0idHJfY2xhc3NpZmllciIpCiAgbW9kZWwuY29tcGlsZShvcHRpbWl6ZXI9ImFkYW0iLAogICAgICAgICAgICAgICAgbG9zcz0iYmluYXJ5X2Nyb3NzZW50cm9weSIsCiAgICAgICAgICAgICAgICBtZXRyaWNzPVsiYWNjdXJhY3kiXSkKICByZXR1cm4gbW9kZWwKCnByaW50KHRyX21vZGVsX2ZuKCkuc3VtbWFyeShsaW5lX2xlbmd0aD05MCkpCgppbWRiX3RyID0gdGYua2VyYXMud3JhcHBlcnMuc2Npa2l0X2xlYXJuLktlcmFzQ2xhc3NpZmllcih0cl9tb2RlbF9mbikKaWYgb3MucGF0aC5leGlzdHModHJfbW9kZWxfZmlsZSk6CiAgIyBSZXN0b3JlIHRoZSBtb2RlbCB3aXRoIHdyYXBwZXIuCiAgaW1kYl90ci5tb2RlbCA9IHRmLmtlcmFzLm1vZGVscy5sb2FkX21vZGVsKHRyX21vZGVsX2ZpbGUpCiAgaW1kYl90ci5jbGFzc2VzXyA9IG5wLmFycmF5KFswLCAxXSkKZWxzZToKICBpbWRiX3RyID0gdGYua2VyYXMud3JhcHBlcnMuc2Npa2l0X2xlYXJuLktlcmFzQ2xhc3NpZmllcih0cl9tb2RlbF9mbikKICBtZXRyaWNzID0gaW1kYl90ci5maXQoCiAgICB4PXNlcV90cmFpbl9wYWRkZWQsIHk9aW1kYl95X3RyYWluLAogICAgYmF0Y2hfc2l6ZT0yNTYsIGVwb2Nocz0yMCwKICAgIHZhbGlkYXRpb25fZGF0YT0oc2VxX3Rlc3RfcGFkZGVkLCBpbWRiX3lfdGVzdCksCiAgICB2YWxpZGF0aW9uX3N0ZXBzPTIwLAogICAgY2FsbGJhY2tzPVsKICAgICAgdGYua2VyYXMuY2FsbGJhY2tzLkVhcmx5U3RvcHBpbmcobW9uaXRvcj0idmFsX2xvc3MiLCBwYXRpZW5jZT0yKSwKICAgICAgdGYua2VyYXMuY2FsbGJhY2tzLk1vZGVsQ2hlY2twb2ludCh0cl9tb2RlbF9maWxlLCBtb25pdG9yPSJ2YWxfbG9zcyIsIHNhdmVfYmVzdF9vbmx5PVRydWUpCiAgICBdLAogICAgdmVyYm9zZT0yKQoKaW1kYl90cl95aGF0ID0gaW1kYl90ci5wcmVkaWN0X3Byb2JhKHNlcV90ZXN0X3BhZGRlZClbOiwxXQppbWRiX3RyX3ByZWQgPSAoaW1kYl90cl95aGF0ID4gLjUpLmFzdHlwZShpbnQpCgpwcmludChjbGFzc2lmaWNhdGlvbl9yZXBvcnQoaW1kYl95X3Rlc3QsIGltZGJfdHJfcHJlZCkpCnByaW50KHJvY19hdWNfc2NvcmUoaW1kYl95X3Rlc3QsIGltZGJfdHJfeWhhdCkpCmBgYAoKT3VyIE5OIG1vZGVsIHdpdGggdHJhbnNmZXIgbGVhcm5pbmcgaGFzIHNpbWlsYXIgQVVDIHNjb3JlIHRvIHRoZSB2YW5pbGxhIE5OLgpMZXQncyB1c2UgZXhwbGFuYXRpb24gbW9kZWxpbmcgdG8gc2VlIGlmIHRoZXJlIGlzIGFueSBhY3R1YWwgZGlmZmVyZW5jZS4KCmBgYHtweXRob24gbGltZV9pbWRiX3RyYW5zZmVyX2xlYXJuaW5nfQpkZWYgdHJfcHJlZGljdF9mbih0ZXh0KToKICAjIFRoaXMgaXMgZm9yIHNrbGVhcm4gd3JhcHBlciBvbmx5LgogIHNlcSA9IHRva2VuaXplci50ZXh0c190b19zZXF1ZW5jZXModGV4dCkKICBzZXEgPSBwYWRfc2VxdWVuY2VzKHNlcSwgcGFkZGluZz0icG9zdCIsIG1heGxlbj1tYXhsZW4pCiAgcmV0dXJuIGltZGJfdHIucHJlZGljdF9wcm9iYShzZXEpCgppbWRiX3RyX2V4cGxhaW5lciA9IExpbWVUZXh0RXhwbGFpbmVyKGNsYXNzX25hbWVzPVsiTmVnYXRpdmUiLCAiUG9zaXRpdmUiXSkKCiMgRXhwbGFpbiB0aGUgc2FtZSBleGFtcGxlcyBhcyBpbiBSRi4KaW1kYl90cl90cF9leHAgPSBpbWRiX3RyX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIGltZGJfcmV2aWV3c190ZXN0W2ltZGJfcmZfdHBfaWR4WzBdXSwgdHJfcHJlZGljdF9mbiwgbnVtX2ZlYXR1cmVzPTYpCmltZGJfdHJfZnBfZXhwID0gaW1kYl90cl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICBpbWRiX3Jldmlld3NfdGVzdFtpbWRiX3JmX2ZwX2lkeFswXV0sIHRyX3ByZWRpY3RfZm4sIG51bV9mZWF0dXJlcz02KQoKaW1kYl90cl90cF9leHAuc2F2ZV90b19maWxlKCIvdG1wL2V4cGxhaW5fdGV4dF90cl90cC5odG1sIikKaW1kYl90cl9mcF9leHAuc2F2ZV90b19maWxlKCIvdG1wL2V4cGxhaW5fdGV4dF90cl9mcC5odG1sIikKYGBgCgpGb3IgdGhlIHNhbWUgcG9zaXRpdmUgcmV2aWV3LAphZ2FpbiB0aGUgbW9kZWwgc2hvd3Mgb3Zlci1jb25maWRlbmNlLgpFdmVuIHRoZSBkb25pbWFudCB3b3JkcyBhcmUgdGhlIHNhbWUuCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGV4dF90cl90cC5odG1sIikpCmBgYAoKPGJyPgoKRm9yIHRoZSBuZWdhdGl2ZSByZXZpZXcsCmludGVyZXN0aW5nbHksCnRoZSB0cmFuc2ZlciBsZWFybmluZyBOTiBpbmRlZWQgbWFrZXMgYSBjb3JyZWN0IHByZWRpY3Rpb24gb2YgbmVnYXRpdmUgbGFiZWwuClRoZSB3b3JkIGBib3JlYCBiZWNvbWVzIHRoZSBtYWluIGRyaXZpbmcgZm9yY2UgdG8gbG93ZXIgZG93biB0aGUgc2NvcmUuCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChwYXJzZV9saW1lX2h0bWxfb3V0cHV0KCIvdG1wL2V4cGxhaW5fdGV4dF90cl9mcC5odG1sIikpCmBgYAoKPGJyPgoKIyMjIEV4cGxhaW4gUmVjdXJyZW50IE5ldXJhbCBOZXRzCgpBcyBhIGZpbmFsIGV4ZXJjaXNlIG9uIHRleHQgY2xhc3NpZmljYXRpb24sCmxldCdzIGV4cGVyaW1lbnQgdGhlIGV4cGxhbmF0aW9uIG1vZGVsaW5nIHdpdGggYSByZWN1cnJlbnQgbmV1cmFsIG5ldHdvcmsgKFJOTikKUk5OIGlzIGtub3duIHRvIGJlIGFibGUgdG8gY2FwdHVyZSBzZXF1ZW50aWFsIGRlcGVuZGVuY2llcyBiZXR0ZXIgdGhhbiBuZ3JhbSBiYWctb2Ytd29yZHMgYXBwcm9hY2guCl5bTm90ZSB0aGF0LCBldmVuIGZvciBhIHNpbmdsZSByZWN1cnJlbnQgbGF5ZXIsIHRyYWluaW5nIGEgUk5OIHdpbGwgYmUgcHJvaGliaXRpdmVseSBzbG93IHdpdGhvdXQgYSBHUFUuXQoKYGBge3B5dGhvbiBpbWRiX3Jubn0Kcm5uX21vZGVsX2ZpbGUgPSBvcy5wYXRoLmpvaW4obW9kZWxfZGlyLCAidGV4dF9jbGZfcm5uLmg1IikKCmRlZiBybm5fbW9kZWxfZm4oKToKICBlbWJlZGRpbmdfc2l6ZSA9IGdsb3ZlLnNoYXBlWzFdCiAgbW9kZWwgPSB0Zi5rZXJhcy5TZXF1ZW50aWFsKFsKICAgIHRmLmtlcmFzLmxheWVycy5FbWJlZGRpbmcoCiAgICAgIHZvY2FiX3NpemUsIGVtYmVkZGluZ19zaXplLCBpbnB1dF9sZW5ndGg9bWF4bGVuLAogICAgICBlbWJlZGRpbmdzX2luaXRpYWxpemVyPXRmLmtlcmFzLmluaXRpYWxpemVycy5Db25zdGFudChnbG92ZSksCiAgICAgIHRyYWluYWJsZT1UcnVlLCBtYXNrX3plcm89VHJ1ZSwgbmFtZT0iZ2xvdmVfZW1iZWRkaW5nIiksCiAgICB0Zi5rZXJhcy5sYXllcnMuR1JVKDY0LCBkcm9wb3V0PS4yLCBuYW1lPSJHUlUiKSwKICAgIHRmLmtlcmFzLmxheWVycy5EZW5zZSgxLCBhY3RpdmF0aW9uPSJzaWdtb2lkIiwgbmFtZT0ic2lnbW9pZCIpCiAgXSwgbmFtZT0icm5uX2NsYXNzaWZpZXIiKQogIG1vZGVsLmNvbXBpbGUob3B0aW1pemVyPSJhZGFtIiwKICAgICAgICAgICAgICAgIGxvc3M9ImJpbmFyeV9jcm9zc2VudHJvcHkiLAogICAgICAgICAgICAgICAgbWV0cmljcz1bImFjY3VyYWN5Il0pCiAgcmV0dXJuIG1vZGVsCgpwcmludChybm5fbW9kZWxfZm4oKS5zdW1tYXJ5KGxpbmVfbGVuZ3RoPTkwKSkKCmltZGJfcm5uID0gdGYua2VyYXMud3JhcHBlcnMuc2Npa2l0X2xlYXJuLktlcmFzQ2xhc3NpZmllcihybm5fbW9kZWxfZm4pCmlmIG9zLnBhdGguZXhpc3RzKHJubl9tb2RlbF9maWxlKToKICAjIFJlc3RvcmUgdGhlIG1vZGVsIHdpdGggd3JhcHBlci4KICBpbWRiX3Jubi5tb2RlbCA9IHRmLmtlcmFzLm1vZGVscy5sb2FkX21vZGVsKHJubl9tb2RlbF9maWxlKQogIGltZGJfcm5uLmNsYXNzZXNfID0gbnAuYXJyYXkoWzAsIDFdKQplbHNlOgogIG1ldHJpY3MgPSBpbWRiX3Jubi5maXQoCiAgICB4PXNlcV90cmFpbl9wYWRkZWQsIHk9aW1kYl95X3RyYWluLAogICAgYmF0Y2hfc2l6ZT0zMiwgZXBvY2hzPTEwLAogICAgdmFsaWRhdGlvbl9kYXRhPShzZXFfdGVzdF9wYWRkZWQsIGltZGJfeV90ZXN0KSwKICAgIHZhbGlkYXRpb25fc3RlcHM9MjAsCiAgICBjYWxsYmFja3M9WwogICAgICB0Zi5rZXJhcy5jYWxsYmFja3MuRWFybHlTdG9wcGluZyhtb25pdG9yPSJ2YWxfbG9zcyIsIHBhdGllbmNlPTIpLAogICAgICB0Zi5rZXJhcy5jYWxsYmFja3MuTW9kZWxDaGVja3BvaW50KHJubl9tb2RlbF9maWxlLCBtb25pdG9yPSJ2YWxfbG9zcyIsIHNhdmVfYmVzdF9vbmx5PVRydWUpCiAgICBdLAogICAgdmVyYm9zZT0yKQoKaW1kYl9ybm5feWhhdCA9IGltZGJfcm5uLnByZWRpY3RfcHJvYmEoc2VxX3Rlc3RfcGFkZGVkKVs6LDFdICAjIEludGVyZW5jZSBvZiBSTk4gdGFrZSB0aW1lLgppbWRiX3Jubl9wcmVkID0gKGltZGJfcm5uX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydChpbWRiX3lfdGVzdCwgaW1kYl9ybm5fcHJlZCkpCnByaW50KHJvY19hdWNfc2NvcmUoaW1kYl95X3Rlc3QsIGltZGJfcm5uX3loYXQpKQpgYGAKClNpbmNlIHRoZSBkYXRhc2V0IGlzIHJhdGhlciBzbWFsbCwKd2UgZGlkbid0IHNlZSBhbnkgYWR2YW50YWdlIG9mIFJOTiBvdmVyIGEgc2ltcGxlIHBvb2xpbmcgZW1iZWRkaW5nIG1vZGVsLgpJbmRlZWQgaXQncyBhY2N1cmFjeSBpcyBzbGlnaHRseSB3b3JzZSB0aGFuIHRoZSBvdGhlciB0d28gTk4gbW9kZWxzIG9uIHRoZSB0ZXN0aW5nIGRhdGFzZXQuClRoYXQncyBzZWUgaG93IHRoZSBleHBsYW5hdGlvbiBjYW4gZGlmZmVyLCBhZ2FpbiwgZm9yIHRoZSBzYW1lIHR3byBleGFtcGxlczoKCmBgYHtweXRob24gbGltZV9pbWRiX3Jubn0KZGVmIHJubl9wcmVkaWN0X2ZuKHRleHQpOgogICMgVGhpcyBpcyBmb3Igc2tsZWFybiB3cmFwcGVyIG9ubHkuCiAgc2VxID0gdG9rZW5pemVyLnRleHRzX3RvX3NlcXVlbmNlcyh0ZXh0KQogIHNlcSA9IHBhZF9zZXF1ZW5jZXMoc2VxLCBwYWRkaW5nPSJwb3N0IiwgbWF4bGVuPW1heGxlbikKICByZXR1cm4gaW1kYl9ybm4ucHJlZGljdF9wcm9iYShzZXEpCgppbWRiX3Jubl9leHBsYWluZXIgPSBMaW1lVGV4dEV4cGxhaW5lcihjbGFzc19uYW1lcz1bIk5lZ2F0aXZlIiwgIlBvc2l0aXZlIl0pCgojIEV4cGxhaW4gdGhlIHNhbWUgZXhhbXBsZXMgYXMgaW4gUkYuCmltZGJfcm5uX3RwX2V4cCA9IGltZGJfcm5uX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIGltZGJfcmV2aWV3c190ZXN0W2ltZGJfcmZfdHBfaWR4WzBdXSwgcm5uX3ByZWRpY3RfZm4sIG51bV9mZWF0dXJlcz02KQppbWRiX3Jubl9mcF9leHAgPSBpbWRiX3Jubl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICBpbWRiX3Jldmlld3NfdGVzdFtpbWRiX3JmX2ZwX2lkeFswXV0sIHJubl9wcmVkaWN0X2ZuLCBudW1fZmVhdHVyZXM9NikKCmltZGJfcm5uX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90ZXh0X3Jubl90cC5odG1sIikKaW1kYl9ybm5fZnBfZXhwLnNhdmVfdG9fZmlsZSgiL3RtcC9leHBsYWluX3RleHRfcm5uX2ZwLmh0bWwiKQpgYGAKClRoZSBzYW1lIG92ZXItY29uZmlkZW5jZSBmb3IgYWxsIE5OIG1vZGVscyBvbiB0aGlzIHBhcnRpY3VsYXIgcG9zaXRpdmUgcmV2aWV3LgoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RleHRfcm5uX3RwLmh0bWwiKSkKYGBgCgo8YnI+CgpGb3IgdGhlIG5lZ2F0aXZlIHJldmlldywKUk5OIGFsc28gY29ycmVjdGx5IHByZWRpY3QgdGhlIGxhYmVsLgpUaGlzIHRpbWUgd2l0aCBldmVuIG1vcmUgY29uZmlkZW5jZSB0aGFuIE5OIHdpdGggcHJlLXRyYWluZWQgZW1iZWRkaW5ncy4KCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKHBhcnNlX2xpbWVfaHRtbF9vdXRwdXQoIi90bXAvZXhwbGFpbl90ZXh0X3Jubl9mcC5odG1sIikpCmBgYAoKPGJyPgoKIyMjIEZyb20gRXhwbGFuYXRpb24gdG8gVHJ1c3QKClRocm91Z2hvdXQgdGhlIGV4ZXJjaXNlIGFib3ZlIHdlIG9ubHkgZGVtb25zdHJhdGUgd2l0aCB0d28gZXhhbXBsZXMsCnNvIG5vdGhpbmcgcmVhbGx5IGNvbmNsdXNpdmUgaGVyZSBhcyB3aGljaCBtb2RlbCBpcyBtb3JlIHJlYXNvbmFibGUgaW4gbWFraW5nIHRoZWlyIGRlY2lzaW9uLgpCdXQgd2l0aCBtb3JlIGludmVzdGlnYXRpb24gdGhlcmUgbWF5IGJlIG1vcmUgaW5zaWdodHMgb24gd2hpY2ggbW9kZWwgY2FuIGJlIHRydXN0ZWQgbW9yZSB0aGFuIHRoZSBvdGhlcnMuCgpXZSBzdW1tYXJpemUgdGhlIGJlbmVmaXQgb2YgZXhwbGFuYXRpb24gbW9kZWxpbmcgaGVyZS4KSW4gZ2VuZXJhbCBpdCBhbGxvd3MgdXMuLi4KCjEuIFRvIHJlYXNvbiB0aGUgbW9kZWwgYmVoYXZpb3IgYXQgYSBzaW5nbGUgaW5zdGFuY2UgbGV2ZWwKMi4gVG8gaW52ZXN0aWdhdGUgdW5yZWFzb25hYmxlIGJlaGF2aW9yIHN1Y2ggdGhhdCB3ZSBjYW4gZnVydGhlciBpbXByb3ZlIHRoZSBvcmlnaW5hbCBtb2RlbCB3aXRoIGZlYXR1cmUgZW5naW5lZXJpbmcKMy4gVG8gZGlmZmVyZW50aWF0ZSBkaWZmZXJlbnQgbW9kZWxzIHdpdGggc2ltaWxhciB0ZXN0aW5nIHNjb3Jlcwo0LiBUbyBidWlsZCB0cnVzdCBvbiBhIG1vZGVsLCBlc3BlY2lhbGx5IGZvciB0aGUgZW5kIHVzZXIsIHRvIGJldHRlciBmb3JtdWxhdGUgdGhlIHN1YnNlcXVlbnQgYWN0aW9uIGl0ZW0KCiMjIE9uIFRhYnVsYXIgRGF0YSBDbGFzc2lmaWVyCgpMb3RzIG9mIGRhdGEgY2FuIGJlIHJlcHJlc2VudGVkIGluIHRhYnVsYXIgZm9ybWF0LgpIZXJlIHdlIHdpbGwgdXNlIFtVQ0kgSGVhcnQgRGlzZWFzZSBkYXRhc2V0XShodHRwczovL2FyY2hpdmUuaWNzLnVjaS5lZHUvbWwvZGF0YXNldHMvSGVhcnQrRGlzZWFzZSkgZm9yIGRlbW8uClBhcnRpY3VsYXJseSwKd2UgdXNlIHRoZSBDbGV2ZWxhbmQgZGF0YXNldCB3aGljaCBpcyBjb21tb25seSB1c2VkIGluIG1hY2hpbmUgbGVhcm5pbmcgcmVzZWFyY2guCl5bVi5BLiBNZWRpY2FsIENlbnRlciwgTG9uZyBCZWFjaCBhbmQgQ2xldmVsYW5kIENsaW5pYyBGb3VuZGF0aW9uOlJvYmVydCBEZXRyYW5vLCBNLkQuLCBQaC5ELl0KCmBgYHtweXRob24gbWF5YmVfZG93bmxvYWRfdWNpaGQsIHJlc3VsdHM9ImhpZGUifQp1Y2loZF9yZW1vdGVfcGF0aCA9ICJodHRwczovL2FyY2hpdmUuaWNzLnVjaS5lZHUvbWwvbWFjaGluZS1sZWFybmluZy1kYXRhYmFzZXMvaGVhcnQtZGlzZWFzZS9wcm9jZXNzZWQuY2xldmVsYW5kLmRhdGEiCnVjaWhkX2ZuYW1lID0gb3MucGF0aC5iYXNlbmFtZSh1Y2loZF9yZW1vdGVfcGF0aCkKdWNpaGRfbG9jYWxfcGF0aCA9IG9zLnBhdGguam9pbihjYWNoZV9kaXIsICJkYXRhc2V0cyIsIHVjaWhkX2ZuYW1lKQoKaWYgbm90IG9zLnBhdGguZXhpc3RzKHVjaWhkX2xvY2FsX3BhdGgpOgogIF8gPSB0Zi5rZXJhcy51dGlscy5nZXRfZmlsZShmbmFtZT11Y2loZF9mbmFtZSwgb3JpZ2luPXVjaWhkX3JlbW90ZV9wYXRoLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBleHRyYWN0PUZhbHNlLCBjYWNoZV9kaXI9Y2FjaGVfZGlyKQpgYGAKClRoZSBkYXRhc2V0IGNvbnRhaW5zIGJvdGggbnVtZXJpY2FsIGFuZCBjYXRlZ29yaWNhbCBmZWF0dXJlcwooYWxsIGVuY29kZWQgaW4gbnVtZXJpY3MgYWxyZWFkeSwgcGxlYXNlIHJlZmVyIHRvIHRoZSBpbi1saW5lIGNvbW1lbnRzIGZvciBkb2N1bWVudGF0aW9uKS4KSXQgaXMgdGlueSBpbiBib3RoIG51bWJlciBvZiBmZWF0dXJlcyBhbmQgbnVtYmVyIG9mIGV4YW1wbGVzLgpCdXQgYXMgYSBkZW1vIGNhc2UgaXQgc2hvdWxkIHNlcnZlIHdlbGwgdGhlIHB1cnBvc2UuCgpgYGB7cHl0aG9uIHByZXByb2Nlc3NfdWNpaGR9CnVjaWhkX2F0dHIgPSBbCiAgImFnZSIsCiAgInNleCIsICAgICAgIyAwID0gZmVtYWxlIDEgPSBtYWxlCiAgImNwIiwgICAgICAgIyBjaGVzdCBwYWluIHR5cGUgMTogdHlwaWNhbCBhbmdpbmEgMjogYXR5cGljYWwgYW5naW5hIDM6IG5vbi1hbmdpbmFsIHBhaW4gNDogYXN5bXB0b21hdGljCiAgInRyZXN0YnBzIiwgIyByZXN0aW5nIGJsb29kIHByZXNzdXJlIChpbiBtbSBIZyBvbiBhZG1pc3Npb24gdG8gdGhlIGhvc3BpdGFsKQogICJjaG9sIiwgICAgICMgc2VydW0gY2hvbGVzdG9yYWwgaW4gbWcvZGwKICAiZmJzIiwgICAgICAjIChmYXN0aW5nIGJsb29kIHN1Z2FyID4gMTIwIG1nL2RsKSAoMSA9IHRydWU7IDAgPSBmYWxzZSkKICAicmVzdGVjZyIsICAjIHJlc3RpbmcgZWxlY3Ryb2NhcmRpb2dyYXBoaWMgcmVzdWx0cyAwOiBub3JtYWwgMTogaGF2aW5nIFNULVQgd2F2ZSBhYm5vcm1hbGl0eSAyOiBzaG93aW5nIHByb2JhYmxlIG9yIGRlZmluaXRlIGxlZnQgdmVudHJpY3VsYXIgaHlwZXJ0cm9waHkgYnkgRXN0ZXMnIGNyaXRlcmlhCiAgInRoYWxhY2giLCAgIyBtYXhpbXVtIGhlYXJ0IHJhdGUgYWNoaWV2ZWQKICAiZXhhbmciLCAgICAjIGV4ZXJjaXNlIGluZHVjZWQgYW5naW5hICgxID0geWVzOyAwID0gbm8pCiAgIm9sZHBlYWsiLCAgIyBTVCBkZXByZXNzaW9uIGluZHVjZWQgYnkgZXhlcmNpc2UgcmVsYXRpdmUgdG8gcmVzdAogICJzbG9wZSIsICAgICMgdGhlIHNsb3BlIG9mIHRoZSBwZWFrIGV4ZXJjaXNlIFNUIHNlZ21lbnQKICAiY2EiLCAgICAgICAjIG51bWJlciBvZiBtYWpvciB2ZXNzZWxzICgwLTMpIGNvbG9yZWQgYnkgZmxvdXJvc2NvcHkKICAidGhhbCIsICAgICAjIDMgPSBub3JtYWw7IDYgPSBmaXhlZCBkZWZlY3Q7IDcgPSByZXZlcnNhYmxlIGRlZmVjdAogICJsYWJlbCIgICAgICMgZGlhZ25vc2lzIG9mIGhlYXJ0IGRpc2Vhc2UgKGFuZ2lvZ3JhcGhpYyBkaXNlYXNlIHN0YXR1cykgMDogPCA1MCUgZGlhbWV0ZXIgbmFycm93aW5nIDEtNDogPiA1MCUgZGlhbWV0ZXIgbmFycm93aW5nCl0KdWNpaGQgPSBwZC5yZWFkX2Nzdih1Y2loZF9sb2NhbF9wYXRoLCBoZWFkZXI9Tm9uZSwgbmFtZXM9dWNpaGRfYXR0ciwgbmFfdmFsdWVzPSI/IikKY2F0ZWdvcmljYWxfYXR0ciA9IFsic2V4IiwgImNwIiwgImZicyIsICJyZXN0ZWNnIiwgImV4YW5nIiwgInRoYWwiXQpmb3IgY29sIGluIGNhdGVnb3JpY2FsX2F0dHI6CiAgdWNpaGRbY29sXSA9IHVjaWhkW2NvbF0uYXN0eXBlKCJjYXRlZ29yeSIpCgojIENsZWFuIGxhYmVsLgp1Y2loZC5sb2NbdWNpaGRbImxhYmVsIl0gPiAxLCAibGFiZWwiXSA9IDEKCnByaW50KHVjaWhkLnNoYXBlKQpwcmludCh1Y2loZC5ncm91cGJ5KCJsYWJlbCIpLnNpemUoKSkgICMgTGFiZWwgZGlzdHJpYnV0aW9uLgpwcmludCh1Y2loZC5oZWFkKCkpCmBgYAoKIyMjIEV4cGxhaW4gUmFuZG9tIEZvcmVzdAoKQWdhaW4gd2UgdHJ5IHRvIGV4cGxhaW4gdHJlZSBlbnNlbWJlbHMuCgpgYGB7cHl0aG9uIHVjaWhkX3JmfQojIHNrbGVhcm4ncyBpbXBsZW1lbnRhdGlvbiBvZiBSRiBkb2Vzbid0IGFsbG93IG1pc3NpbmcgdmFsdWUuCiMgRm9yIGNhdGVnb3JpY2FsIChhcyBzdHJpbmcpIHdlIGNhbiBsZWF2ZSBvbmUgc3BlY2lhbCBjYXRlZ29yeSBmb3IgbWlzc2luZywKIyBidXQgZm9yIG51bWVyaWNhbCB3ZSBuZWVkIHRvIGRvIHNvbWUgc3BlY2lhbCBlbmNvZGluZyBvciBpbXB1dGF0aW9uLgp1Y2loZF8yID0gdWNpaGQuY29weSgpCnVjaWhkXzIubG9jW3VjaWhkXzJbImNhIl0uaXNuYSgpLCAiY2EiXSA9IC0xICAjIEVuY29kZSBtaXNzaW5nIG51bWVyaWNhbC4KCiMgT25lLWhvdCBlbmNvZGUgYWxsIGNhdGVnb3JpY2FsIGZlYXR1cmVzLgp1Y2loZF8yID0gcGQuZ2V0X2R1bW1pZXModWNpaGRfMiwgY29sdW1ucz1jYXRlZ29yaWNhbF9hdHRyLCBkdW1teV9uYT1UcnVlKQp1Y2loZF95ID0gdWNpaGRfMi5wb3AoImxhYmVsIikKdWNpaGRfWF90cmFpbiwgdWNpaGRfWF90ZXN0LCB1Y2loZF95X3RyYWluLCB1Y2loZF95X3Rlc3QgPSB0cmFpbl90ZXN0X3NwbGl0KAogIHVjaWhkXzIsIHVjaWhkX3kudmFsdWVzLCB0ZXN0X3NpemU9LjMsIHJhbmRvbV9zdGF0ZT02NCkKCnVjaWhkX3JmID0gUmFuZG9tRm9yZXN0Q2xhc3NpZmllcihuX2VzdGltYXRvcnM9MTAwLCByYW5kb21fc3RhdGU9NjQpCl8gPSB1Y2loZF9yZi5maXQodWNpaGRfWF90cmFpbiwgdWNpaGRfeV90cmFpbikKCnVjaWhkX3JmX3loYXQgPSB1Y2loZF9yZi5wcmVkaWN0X3Byb2JhKHVjaWhkX1hfdGVzdClbOiwxXQp1Y2loZF9yZl9wcmVkID0gdWNpaGRfcmYucHJlZGljdCh1Y2loZF9YX3Rlc3QpCgpwcmludChjbGFzc2lmaWNhdGlvbl9yZXBvcnQodWNpaGRfeV90ZXN0LCB1Y2loZF9yZl9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZSh1Y2loZF95X3Rlc3QsIHVjaWhkX3JmX3loYXQpKQpgYGAKCkFzIG9uZSBjYW4gc2VlIFJGIHBlcmZvcm1zIHZlcnkgd2VsbCBvbiB0aGlzIGRhdGFzZXQuCgpUbyBleHBsYWluIGEgbW9kZWwgdHJhaW5lZCB3aXRoIG51bWVyaWNhbCBmZWF0dXJlcywKYGxpbWVgIGJ5IGRlZmF1bHQgd2lsbCBkaXNjcmV0aXplIGNvbnRpbm91cyB2YXJpYWJsZXMgaW50byBxdWFudGlsZXMgZm9yIGVhc2Ugb2YgaW50ZXJwcmV0YXRpb24uCkRpc2NyZXRpemF0aW9uIGlzIGRvbmUgdXNpbmcgc3RhdGlzdGljcyBkZXJpdmVkIGZyb20gdGhlIHRyYWluaW5nIGRhdGFzZXQuCgpgYGB7cHl0aG9uIGxpbWVfdWNpaGRfcmZ9CmZyb20gbGltZS5saW1lX3RhYnVsYXIgaW1wb3J0IExpbWVUYWJ1bGFyRXhwbGFpbmVyCgpjYXRfaW5kID0gW2kgZm9yIGksIGNvbCBpbiBlbnVtZXJhdGUodWNpaGRfMi5jb2x1bW5zKSBpZiAiXyIgaW4gY29sXQp1Y2loZF9yZl9leHBsYWluZXIgPSBMaW1lVGFidWxhckV4cGxhaW5lcigKICB1Y2loZF9YX3RyYWluLnZhbHVlcywgY2xhc3NfbmFtZXM9WyJOZWdhdGl2ZSIsICJQb3NpdGl2ZSJdLAogIGZlYXR1cmVfbmFtZXM9dWNpaGRfMi5jb2x1bW5zLAogIGNhdGVnb3JpY2FsX2ZlYXR1cmVzPWNhdF9pbmQpCgp1Y2loZF9yZl90cF9pZHggPSBucC53aGVyZShucC5sb2dpY2FsX2FuZCh1Y2loZF9yZl9wcmVkID09IDEsIHVjaWhkX3lfdGVzdCA9PSAxKSlbMF0KdWNpaGRfcmZfZnBfaWR4ID0gbnAud2hlcmUobnAubG9naWNhbF9hbmQodWNpaGRfcmZfcHJlZCA9PSAxLCB1Y2loZF95X3Rlc3QgPT0gMCkpWzBdCgojIFdlIHRha2Ugb25lIHRydWUgcG9zaXRpdmUgYW5kIG9uZSBmYWxzZSBwb3NpdGl2ZSBmb3IgZXhhbXBsZXMuCnVjaWhkX3JmX3RwX2V4cCA9IHVjaWhkX3JmX2V4cGxhaW5lci5leHBsYWluX2luc3RhbmNlKAogIHVjaWhkX1hfdGVzdC5pbG9jW3VjaWhkX3JmX3RwX2lkeFswXV0sIHVjaWhkX3JmLnByZWRpY3RfcHJvYmEsIG51bV9mZWF0dXJlcz00KQp1Y2loZF9yZl9mcF9leHAgPSB1Y2loZF9yZl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICB1Y2loZF9YX3Rlc3QuaWxvY1t1Y2loZF9yZl9mcF9pZHhbMF1dLCB1Y2loZF9yZi5wcmVkaWN0X3Byb2JhLCBudW1fZmVhdHVyZXM9NCkKCnVjaWhkX3JmX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90YWJfcmZfdHAuaHRtbCIpCnVjaWhkX3JmX2ZwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90YWJfcmZfZnAuaHRtbCIpCmBgYAoKRm9sbG93aW5nIHRoZSBzYW1lIGlkZWEgaW4gb3VyIGRpc2N1c3Npb24gb24gdGV4dCBjbGFzc2lmaWVycywKd2UgY2hvb3NlIHR3byBleGFtcGxlcywKb25lIHRydWUgcG9zaXRpdmUgYW5kIHRoZSBvdGhlciBmYWxzZSBwb3NpdGl2ZSwKZnJvbSB0aGUgUkYgcHJlZGljdGlvbnMgdG8gZGVtb25zdHJhdGUgZXhwbGFuYXRpb24gbW9kZWxpbmcuCgojIyMjIEEgVHJ1ZSBQb3NpdGl2ZSBQcmVkaWN0aW9uIEV4cGxhaW5lZCB7LX0KCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKHBhcnNlX2xpbWVfaHRtbF9vdXRwdXQoIi90bXAvZXhwbGFpbl90YWJfcmZfdHAuaHRtbCIpKQpgYGAKCjxicj4KClRoZSBleHBsYW5hdGlvbiBzdWdnZXN0cyBzZXZlcmFsIGRvbWluYW50IGZlYXR1cmVzIHRvd2FyZCB0aGUgcG9zaXRpdmUuCkZvciBjYXRlZ29yaWNhbHMgZWFjaCBjYXRlZ29yeSBzZXJ2ZXMgYXMgaW5kaXZpZHVhbCBjb250cmlidXRpb24gZm9yIGV4cGxhbmF0aW9uLgpUaGlzIGlzIGEgbmF0dXJhbCBjb25zZXF1ZW5jZSBvZiBvbmUtaG90IGVuY29kaW5nIGluIG91ciBmZWF0dXJlIHNwYWNlLgoKIyMjIyBBIEZhbHNlIFBvc2l0aXZlIFByZWRpY3Rpb24gRXhwbGFpbmVkIHstfQoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RhYl9yZl9mcC5odG1sIikpCmBgYAoKPGJyPgoKRm9yIHRoZSBmYWxzZSBwb3NpdGl2ZSBjYXNlLAp0aGUgbW9kZWwgaXMgbGVzcyBjb25maWRlbnQuClRoZXJlIGFyZSBpbmRlZWQgbW9yZSBmZWF0dXJlcyBkcml2aW5nIG5lZ2F0aXZlbHkuCkJ1dCBvbmUgc3Ryb25nIHBvc2l0aXZlIGNvbnRyaWJ1dGlvbiBmcm9tIHRoZSBmZWF0dXJlIGBjYWAgKG51bWJlciBvZiBtYWpvciB2ZXNzZWxzIGNvbG9yZWQgYnkgZmxvdXJvc2NvcHkpIGNhbmNlbCBvdXQgdGhlIGVudGlyZSBuZWdhdGl2ZSBkcml2aW5nIGZvcmNlcy4KCiMjIyBFeHBsYWluIEdyYWRpZW50IEJvb3N0aW5nIFRyZWVzCgpHcmFkaWVudCBib29zdGluZyB0cmVlcyAoR0JUKSBpcyBhIHBvd2VyZnVsIG1vZGVsIGZhbWlseSBwcm92ZW4gdG8gd29yayBleGNlcHRpb25hbGx5IHdlbGwgaW4gbWFueSBkaWZmZXJlbnQgYXBwbGljYXRpb25zLgpZZXQgZHVlIHRvIGl0cyBlbnNlbWJsaW5nIG5hdHVyZSwKR0JUIGlzIGFsc28gaGFyZCB0byBpbnRyZXByZXQgaW4gZ2VuZXJhbC4KCkhlcmUgd2UgZGVtbyBgbGlnaHRnYm1gJ3MgaW1wbGVtZW50YXRpb24gb2YgR0JUIHdpdGggTElNRSBleHBsYW5hdGlvbi4KCmBgYHtweXRob24gdWNpaGRfbGdifQppbXBvcnQgbGlnaHRnYm0gYXMgbGdiCgp1Y2loZF90ciA9IGxnYi5EYXRhc2V0KHVjaWhkX1hfdHJhaW4sIGxhYmVsPXVjaWhkX3lfdHJhaW4pCnVjaWhkX3RlID0gbGdiLkRhdGFzZXQodWNpaGRfWF90ZXN0LCBsYWJlbD11Y2loZF95X3Rlc3QpCgp1Y2loZF9sZ2JfcGFyYW1zID0gewogICJsZWFybmluZ19yYXRlIjogLjAxLAogICJib29zdGluZ190eXBlIjogImdiZHQiLAogICJvYmplY3RpdmUiOiAiYmluYXJ5IiwKICAibWV0cmljIjogWyJiaW5hcnlfbG9nbG9zcyIsICJhdWMiXSwKICAibnVtX2xlYXZlcyI6IDgsCiAgIm1heF9kZXB0aCI6IDMsCiAgIm1pbl9kYXRhX3Blcl9sZWFmIjogNSwKICAidmVyYm9zZSI6IC0xLAogICJzZWVkIjogNjQKfQoKdWNpaGRfYnN0ID0gbGdiLnRyYWluKAogIHBhcmFtcz11Y2loZF9sZ2JfcGFyYW1zLAogIG51bV9ib29zdF9yb3VuZD0zMDAsIGVhcmx5X3N0b3BwaW5nX3JvdW5kcz0yMCwKICB0cmFpbl9zZXQ9dWNpaGRfdHIsIHZhbGlkX3NldHM9W3VjaWhkX3RlXSwKICB2ZXJib3NlX2V2YWw9MTApCgp1Y2loZF9sZ2JfeWhhdCA9IHVjaWhkX2JzdC5wcmVkaWN0KHVjaWhkX1hfdGVzdCkKdWNpaGRfbGdiX3ByZWQgPSAodWNpaGRfbGdiX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydCh1Y2loZF95X3Rlc3QsIHVjaWhkX2xnYl9wcmVkKSkKcHJpbnQocm9jX2F1Y19zY29yZSh1Y2loZF95X3Rlc3QsIHVjaWhkX2xnYl95aGF0KSkKYGBgCgpJbiB0aGlzIHBhcnRpY3VsYXIgKHJhdGhlciBzbWFsbCkgZGF0YXNldCBSRiBpbmRlZWQgb3V0cGVyZm9ybXMgR0JULgpBcyBhIG1hdHRlciBvZiBmYWN0LApiYXNlZCBvbiBbZXhpc3RpbmcgYmVuY2htYXJrXShodHRwczovL2dpdGh1Yi5jb20vaW50ZXJwcmV0bWwvaW50ZXJwcmV0L3RyZWUvbWFzdGVyL2JlbmNobWFya3MpIGEgc2ltcGxlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbWF5IGhhdmUgYSBldmVuIGhpZ2hlciBzY29yZSBmb3IgdGhpcyBwcm9ibGVtLgpOZXZlcnRoZWxlc3MsCmxldCdzIG1vdmUgb24gdG8gb3VyIGV4cGxhbmF0aW9uIG1vZGVsIHdpdGggTElNRToKCmBgYHtweXRob24gbGltZV91Y2loZF9sZ2J9CmRlZiB1Y2loZF9sZ2JfcHJlZGljdF9mbih4KToKICAjIFdlIG5lZWQgdG8gb3V0cHV0IDIgY29sdW1ucyBmb3IgYmluYXJ5IHByb2IgcHJlZGljdGlvbi4KICBwID0gdWNpaGRfYnN0LnByZWRpY3QoeCkucmVzaGFwZSgtMSwgMSkKICByZXR1cm4gbnAuaHN0YWNrKCgxIC0gcCwgcCkpCgp1Y2loZF9sZ2JfZXhwbGFpbmVyID0gTGltZVRhYnVsYXJFeHBsYWluZXIoCiAgdWNpaGRfWF90cmFpbi52YWx1ZXMsIGNsYXNzX25hbWVzPVsiTmVnYXRpdmUiLCAiUG9zaXRpdmUiXSwKICBmZWF0dXJlX25hbWVzPXVjaWhkXzIuY29sdW1ucywKICBjYXRlZ29yaWNhbF9mZWF0dXJlcz1jYXRfaW5kKQoKIyBXZSB0YWtlIHRoZSBzYW1lIGV4YW1wbGVzIHByZXZpb3VzbHkgZXhwbGFpbmVkIGluIG91ciBSRiBleHBsYW5hdGlvbiBtb2RlbC4KdWNpaGRfbGdiX3RwX2V4cCA9IHVjaWhkX2xnYl9leHBsYWluZXIuZXhwbGFpbl9pbnN0YW5jZSgKICB1Y2loZF9YX3Rlc3QuaWxvY1t1Y2loZF9yZl90cF9pZHhbMF1dLCB1Y2loZF9sZ2JfcHJlZGljdF9mbiwgbnVtX2ZlYXR1cmVzPTQpCnVjaWhkX2xnYl9mcF9leHAgPSB1Y2loZF9sZ2JfZXhwbGFpbmVyLmV4cGxhaW5faW5zdGFuY2UoCiAgdWNpaGRfWF90ZXN0Lmlsb2NbdWNpaGRfcmZfZnBfaWR4WzBdXSwgdWNpaGRfbGdiX3ByZWRpY3RfZm4sIG51bV9mZWF0dXJlcz00KQoKdWNpaGRfbGdiX3RwX2V4cC5zYXZlX3RvX2ZpbGUoIi90bXAvZXhwbGFpbl90YWJfbGdiX3RwLmh0bWwiKQp1Y2loZF9sZ2JfZnBfZXhwLnNhdmVfdG9fZmlsZSgiL3RtcC9leHBsYWluX3RhYl9sZ2JfZnAuaHRtbCIpCmBgYAoKVGhlIGJlaGF2aW9yIG9mIEdCVCBsb29rcyBzaW1pbGFyIHRvIHRoYXQgb2YgUkYgaW4gdGVybXMgb2YgdGhlc2UgdHdvIGV4YW1wbGVzLgoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocGFyc2VfbGltZV9odG1sX291dHB1dCgiL3RtcC9leHBsYWluX3RhYl9sZ2JfdHAuaHRtbCIpKQpgYGAKCjxicj4KCkluIGJvdGggY2FzZSwKdGhlIHZhcmlhYmxlIGBjYWAgaGFzIGEgZG9taW5hbnQgaW1wYWN0IG9uIHRoZSBmaW5hbCBkZWNpc2lvbi4KVGhlIHR3byBtb2Rlc2wgYWxzbyBzaGFyZSB0aGUgc2FtZSBjb25mdXNpb24gYWdhaW5zdCB0aGUgbmVnYXRpdmUgZXhhbXBsZS4KCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKHBhcnNlX2xpbWVfaHRtbF9vdXRwdXQoIi90bXAvZXhwbGFpbl90YWJfbGdiX2ZwLmh0bWwiKSkKYGBgCgo8YnI+CgojIyMjIE9wdGltaXplZCBDYXRlZ29yaWNhbCBFbmNvZGluZyBpbiBgbGlnaHRnYm1gIHstfQoKKipUaGlzIHNlY3Rpb24gaXMgYSBkaWdyZXNzaW9uIG9uIGBsaWdodGdibWAgdXNhZ2UuKioKClNpbmNlIGBsaW1lYCdzIEFQSSByZXF1aXJlcyB1cyB0byBwcmVwYXJlIG91ciBkYXRhc2V0IGluIG9uZS1ob3QgZW5jb2RpbmcgcmVwcmVzZW50YXRpb24sCm91ciBgbGlnaHRnYm1gIGNvZGUgdXNlIHRoZSBzYW1lIGRhdGEgcGlwZWxpbmUgYXMgaW4gYHNjaWtpdC1sZWFybmAgcmFuZG9tIGZvcmVzdC4KQnV0IHRoYXQgaXMgYWN0dWFsbHkgbm90IG9wdGltaXplZCBmb3IgYGxpZ2h0Z2JtYC4KVGhlIGZvbGxvd2luZyBjb2RlIGNodW5rIHNob3djYXNlcyB0aGUgYmVzdCBwcmFjdGljZSBvZiBlbmNvZGluZyBjYXRlZ29yaWNhbHMgaW4gYGxpZ2h0Z2JtYDoKV2UgZG9uJ3QgZW5jb2RlIHRoZW0gYXQgYWxsIQoKYGBge3B5dGhvbiBsZ2JfYmVzdF9wcmFjdGljZX0KIyBXZSBsZWF2ZSBib3RoIG1pc3NpbmdzIGFuZCBjYXRlZ29yaWNhbHMgYXMtaXMgaW4gdGhlIGRhdGFzZXQuCnVjaWhkX3RyYWluLCB1Y2loZF90ZXN0ID0gdHJhaW5fdGVzdF9zcGxpdCh1Y2loZCwgdGVzdF9zaXplPS4zLCByYW5kb21fc3RhdGU9NjQpCnVjaWhkX3RyID0gbGdiLkRhdGFzZXQoCiAgdWNpaGRfdHJhaW4uZHJvcCgibGFiZWwiLCBheGlzPTEpLCBsYWJlbD11Y2loZF90cmFpblsibGFiZWwiXSwKICBjYXRlZ29yaWNhbF9mZWF0dXJlPWNhdGVnb3JpY2FsX2F0dHIsCiAgZnJlZV9yYXdfZGF0YT1GYWxzZSkKdWNpaGRfdGUgPSBsZ2IuRGF0YXNldCgKICB1Y2loZF90ZXN0LmRyb3AoImxhYmVsIiwgYXhpcz0xKSwgbGFiZWw9dWNpaGRfdGVzdFsibGFiZWwiXSwKICBjYXRlZ29yaWNhbF9mZWF0dXJlPWNhdGVnb3JpY2FsX2F0dHIsCiAgZnJlZV9yYXdfZGF0YT1GYWxzZSkKCnVjaWhkX2JzdF8yID0gbGdiLnRyYWluKAogIHBhcmFtcz11Y2loZF9sZ2JfcGFyYW1zLAogIG51bV9ib29zdF9yb3VuZD0zMDAsIGVhcmx5X3N0b3BwaW5nX3JvdW5kcz0yMCwKICB0cmFpbl9zZXQ9dWNpaGRfdHIsIHZhbGlkX3NldHM9W3VjaWhkX3RlXSwKICB2ZXJib3NlX2V2YWw9LTEpCgp1Y2loZF9sZ2JfeWhhdCA9IHVjaWhkX2JzdF8yLnByZWRpY3QodWNpaGRfdGVzdC5kcm9wKCJsYWJlbCIsIGF4aXM9MSkpCnVjaWhkX2xnYl9wcmVkID0gKHVjaWhkX2xnYl95aGF0ID4gLjUpLmFzdHlwZShpbnQpCgpwcmludChyb2NfYXVjX3Njb3JlKHVjaWhkX3Rlc3RbImxhYmVsIl0sIHVjaWhkX2xnYl95aGF0KSkKYGBgCgpUbyBzdW1tYXJpemUsClRoZXJlIGFyZSB0d28gdmVyeSBzcGVjaWFsIHByb3BlcnRpZXMgYWJvdXQgYGxpZ2h0Z2JtYCBhbGdvcml0aG0uCmBsaWdodGdibWAgdHJlYXRzIG1pc3NpbmdzIG5hdGl2ZWx5IGFzIGEgc3BlY2lhbCB0cmVlIHNwbGl0IHBvaW50LgpUaGlzIGFsbG93cyB1cyB0byBrZWVwIHRoZSBvcmlnaW5hbCBtaXNzaW5nIGFzIGlzIGFuZCBpbiBtYW55IGNhc2VzIGNhbiByZXN1bHQgaW4gYmV0dGVyIGFjY3VyYWN5IHRoYW4gaW1wdXRhdGlvbi5eW2B4Z2Jvb3N0YCBpcyB0aGUgZmlyc3QgdG8gaW50cm9kdWNlIHN1Y2ggbWlzc2luZyB0cmVhdG1lbnQgYW1vbmcgYWxsIHRoZSBHQlQgcGFja2FnZS4gYGxpZ2h0Z2JtYCBmb2xsb3dzLl0KCkluIGFkZGl0aW9uLApgbGlnaHRnYm1gIGVuY29kZXMgY2F0ZWdvcmljYWwgdmFyaWFibGVzIGludGVybmFsbHkgaW4gYSBtb3JlIGVmZmljaWVudCB3YXkuClNvIHdlIGRvbid0IGV2ZW4gbmVlZCB0byBkbyBvbmUtaG90IGVuY29kaW5nIG9uIG91ciBvd24uCk9mIGNvdXJzZSBpbiB0aGlzIHRpbnkgZGF0YXNldCB3ZSB3b24ndCBzZWUgYW55IG5vdGljYWJsZSBkaWZmZXJlbmNlLgpCdXQgZm9yIGxhcmdlIGFwcGxpY2F0aW9ucyB0aGUgcGVyZm9ybWFuY2UgaW1wYWN0IGNhbiBiZSBodWdlLgpXaGF0ZXZlciwKYnkgc2tpcHBpbmcgb25lLWhvdCBlbmNvZGluZyBwaXBlbGluZSBvdXIgY29kZSBjYW4gYmUgbXVjaCBuZWF0ZXIgYXMgd2VsbC4KCiMjIE9uIEltYWdlIENsYXNzaWZpZXIKCioqVE9ETzogVXNlIGEgcHJlLXRyYWluZWQgbW9kZWw/KioKCiMgU2hhcGxleSBSZWdyZXNzaW9uIFZhbHVlcwoKKipUT0RPOiBUaGVvcnkgQnJpZWZpbmcgaGVyZS4qKgoKIyBTSEFQCgpATklQUzIwMTdfNzA2MiBwcm9wb3NlIFNIQVAgKCoqU0hhcGxleSBBZGRpdGl2ZSBleFBsYW5hdGlvbnMqKiksCnlldCBhbm90aGVyIGFkZGl0aXZlIGZlYXR1cmUgYXR0cmlidXRpb24gbWV0aG9kIGZvciBtb2RlbCBleHBsYWluYWJpbGl0eS4KSXQgaXMgYSBtb3JlIGdlbmVyYWwgYXBwcm9hY2ggd2hlcmUgTElNRSBpcyBpbmRlZWQgb25seSBhIHNwZWNpYWwgY2FzZSBvZiBpdC4KSnVzdCBsaWtlIExJTUUsCmluIHRoZW9yeSBpdCBjYW4gYmUgYXBwbGllZCB0byAqYW55KiBtYWNoaW5lIGxlYXJuaW5nIG1vZGVsLApidXQgY29tZXMgd2l0aCBhIGN1c3RvbWl6ZWQgZmFzdCBpbXBsZW1lbnRhdGlvbiBwYXJ0aWN1bGFybHkgZm9yIGdyYWRpZW50IGJvb3N0aW5nIHRyZWVzIChHQlQpLgpJdCBzdXBwb3J0cyBBUElzIG9mIHdlbGwta25vd24gR0JUIGxpYnJhcmllcyBzdWNoIGFzCltgeGdib29zdGBdKGh0dHBzOi8vZ2l0aHViLmNvbS9kbWxjL3hnYm9vc3QpLApbYGxpZ2h0Z2JtYF0oaHR0cHM6Ly9naXRodWIuY29tL21pY3Jvc29mdC9MaWdodEdCTSksCmFuZCBbYGNhdGJvb3N0YF0oaHR0cHM6Ly9naXRodWIuY29tL2NhdGJvb3N0L2NhdGJvb3N0KS4KClRoZSBpbnRlcnByZXRhYmlsaXR5IHByb3ZpZGVkIGJ5IFNIQVAgaXMgYWdhaW4gKmxvY2FsKi4KSXQgYXNzaWducyBlYWNoIGZlYXR1cmUgYW4gaW1wb3J0YW5jZSB2YWx1ZSAqZm9yIGEgcGFydGljdWxhciBwcmVkaWN0aW9uLioKSGVuY2UgaXQgcHJvdmlkZXMgZm9yIGFueSBnaXZlbiBtb2RlbCBwcmVkaWN0aW9uIHdoYXQgbWF5IGJlIHRoZSBkcml2aW5nIGZvcmNlIGZvciB0aGUgbW9kZWwgdG8gbWFrZSBzdWNoIHByZWRpY3Rpb24uCgpgc2hhcGAgYWxzbyBjb21lcyB3aXRoIG1vcmUgdmlzdWFsaXphdGlvbiBtZXRob2RzIGZvciBmZWF0dXJlIGludmVzdGlnYXRpb24sCmVzcGVjaWFsbHkgZm9yIGZlYXR1cmUgaW50ZXJhY3Rpb24gZXhwbG9yYXRpb24uCgoqKlRPRE86IFRoZW9yeSBCcmllZmluZyBoZXJlLioqCgojIyBPbiBUZXh0IENsYXNzaWZpZXJzCgojIyMgRXhwbGFpbiBSYW5kb20gRm9yZXN0Cgpgc2hhcC5UcmVlRXhwbGFpbmVyYCBpcyBvcHRpbWl6ZWQgZm9yIEdCVCBidXQgbm90IFJGLgpGb3IgbW9kZWwgd2l0aCBoaWdoIGRpbWVuc2lvbmFsaXR5IGxpa2UgYSBiYWctb2Ytd29yZHMgbW9kZWwgaXQgd2lsbCBzdWZmZXIgZnJvbSBoaWdoIGNvbXB1dGF0aW9uIGNvc3QgZm9yIG5vbi1HQlQgbW9kZWwuCkhlbmNlIHdlIHdpbGwgc2tpcCB0aGUgZGlzY3Vzc2lvbiBvbiBSRiBhbmQgbW92ZSBmb3J3YXJkIHRvIGEgR0JUIGltcGxlbWVudGF0aW9uLgoKIyMjIEV4cGxhaW4gR3JhZGllbnQgQm9vc3RpbmcgVHJlZXMKCkluIHRoZSBwcmV2aW91cyBzZWN0aW9uIHdlIGRpZG4ndCB0cmFpbiBhIEdCVCBmb3IgdGhlIHRleHQgY2xhc3NpZmljYXRpb24gcHJvYmxlbS4KU28gbGV0J3MgcXVpY2tseSBidWlsZCBvbmUgc3VjaCBtb2RlbCBmaXJzdCAod2l0aCB0aGUgc2FtZSBURi1JREYgdmVjdG9yaXphdGlvbiBhcyB3ZSBkaWQgZm9yIHRoZSBSRiBtb2RlbCkuCgpgYGB7cHl0aG9uIGltZGJfbGdifQojIGxpZ2h0Z2JtIGRvZXMgbm90IGFsbG93IHV0Zi04IGVuY29kZWQgZmVhdHVyZSBuYW1lcy4KIyBTaW5jZSBpbXBvcnRhbnQgdG9rZW5zIGFyZSBtb3N0IGxpa2VseSBhc2NpaS1jb21wYXRpYmxlIGZvciBvdXIgZGF0YXNldCwKIyB3ZSBzaW1wbHkgc3RyaXAgbm9uLWFzY2lpIGFzIGEgd29ya2Fyb3VuZCBmb3IgdGhpcyBleGVyY2lzZS4KZGVmIHJlbW92ZV9ub25fYXNjaWkocyk6CiAgcmV0dXJuICIiLmpvaW4oW2kgaWYgb3JkKGkpIDwgMTI4IGVsc2UgIl8iIGZvciBpIGluIHNdKQoKc29ydGVkX3ZvY2FiX2FzY2lpID0gW3JlbW92ZV9ub25fYXNjaWkodikgZm9yIHYgaW4gc29ydGVkX3ZvY2FiXQoKaW1kYl9YX3RyID0gbGdiLkRhdGFzZXQoaW1kYl9YX3RyYWluLCBsYWJlbD1pbWRiX3lfdHJhaW4sIGZlYXR1cmVfbmFtZT1zb3J0ZWRfdm9jYWJfYXNjaWkpCmltZGJfWF90ZSA9IGxnYi5EYXRhc2V0KGltZGJfWF90ZXN0LCBsYWJlbD1pbWRiX3lfdGVzdCwgZmVhdHVyZV9uYW1lPXNvcnRlZF92b2NhYl9hc2NpaSkKCmltZGJfbGdiX3BhcmFtcyA9IHsKICAibGVhcm5pbmdfcmF0ZSI6IC4wNSwKICAiYm9vc3RpbmdfdHlwZSI6ICJnYmR0IiwKICAib2JqZWN0aXZlIjogImJpbmFyeSIsCiAgIm1ldHJpYyI6IFsiYmluYXJ5X2xvZ2xvc3MiLCAiYXVjIl0sCiAgIm51bV9sZWF2ZXMiOiAxNiwKICAibWF4X2RlcHRoIjogNCwKICAibWluX2RhdGFfcGVyX2xlYWYiOiAyMCwKICAidmVyYm9zZSI6IC0xCn0KCmltZGJfbGdiX21vZGVsX2ZpbGUgPSBvcy5wYXRoLmpvaW4obW9kZWxfZGlyLCAidGV4dF9jbGZfbGdiLnR4dCIpCgojIFNhdmUvcmVsb2FkIG1vZGVsIHRvIHNhdmUgbm90ZWJvb2sgcmVuZGVyaW5nIHRpbWUuCmlmIG9zLnBhdGguZXhpc3RzKGltZGJfbGdiX21vZGVsX2ZpbGUpOgogICMgUGFyYW1ldGVycyBhcmUgbm90IGxvYWRlZCBiYWNrPyAoV2hpY2ggY2F1c2UgdGhlIHN1YnNlcXVlbnQgY2FsbCB0byBzaGFwX3ZhbHVlcyBmYWlsLikKICAjIGh0dHBzOi8vZ2l0aHViLmNvbS9taWNyb3NvZnQvTGlnaHRHQk0vaXNzdWVzLzI2MTMKICAjIEFzIGEgd29ya2Fyb3VuZCB3ZSBwYXNzIHRoZSBzYW1lIHBhcmFtZXRlcnMgdG8gcmUtY29uc3RydWN0IHRoZSBtb2RlbC4KICBpbWRiX2JzdCA9IGxnYi5Cb29zdGVyKG1vZGVsX2ZpbGU9aW1kYl9sZ2JfbW9kZWxfZmlsZSwgcGFyYW1zPWltZGJfbGdiX3BhcmFtcykKZWxzZToKICBpbWRiX2JzdCA9IGxnYi50cmFpbigKICAgIHBhcmFtcz1pbWRiX2xnYl9wYXJhbXMsCiAgICBudW1fYm9vc3Rfcm91bmQ9MTAwMCwgZWFybHlfc3RvcHBpbmdfcm91bmRzPTIwLAogICAgdHJhaW5fc2V0PWltZGJfWF90ciwgdmFsaWRfc2V0cz1baW1kYl9YX3RlXSwKICAgIHZlcmJvc2VfZXZhbD0xMDApCiAgXyA9IGltZGJfYnN0LnNhdmVfbW9kZWwoaW1kYl9sZ2JfbW9kZWxfZmlsZSkKCmltZGJfbGdiX3loYXQgPSBpbWRiX2JzdC5wcmVkaWN0KGltZGJfWF90ZXN0KQppbWRiX2xnYl9wcmVkID0gKGltZGJfbGdiX3loYXQgPiAuNSkuYXN0eXBlKGludCkKCnByaW50KGNsYXNzaWZpY2F0aW9uX3JlcG9ydChpbWRiX3lfdGVzdCwgaW1kYl9sZ2JfcHJlZCkpCnByaW50KHJvY19hdWNfc2NvcmUoaW1kYl95X3Rlc3QsIGltZGJfbGdiX3loYXQpKQpgYGAKCkJhc2VkIG9uIHRoZSB0ZXN0aW5nIEFVQyBzY29yZSB3ZSBmaW5kIG91dCB0aGF0IEdCVCBwZXJmb3JtcyBjb21wYXJhYmx5IHRvIG5ldXJhbCBuZXR3b3JrIG1vZGVscy4KCkp1c3QgbGlrZSBSRiB3ZSB3aWxsIGhhdmUgYWNjZXNzIHRvIHRoZSBvdmVyYWxsIGZlYXR1cmUgaW1wb3J0YW5jZSB3aXRoIGEgR0JUIG1vZGVsOgpeW0J5IGRlZmF1bHQgYGxpZ2h0Z2JtYCBjYWxjdWxhdGVzIHRoZSBpbXBvcnRhbmNlIGJ5IGNvdW50aW5nIGhvdyBtYW55IHRpbWVzIGEgZmVhdHVyZSBjb250cmlidXRlcyB0byBhbiBvcHRpbWFsIHNwbGl0IGR1cmluZyB0cmFpbmluZy4KSXQgYWxzbyBzdXBwb3J0cyB0aGUgaW1wdXJpdHktYmFzZWQgYXBwcm9hY2ggd2l0aCBhcmd1bWVudCBgaW1wb3J0YW5jZV90eXBlYCBzZXQgdG8gYCJnYWluImAuXQoKYGBge3B5dGhvbiBpbWRiX2xnYl9mZWF0X2ltcH0KYXggPSBsZ2IucGxvdF9pbXBvcnRhbmNlKGltZGJfYnN0LCBtYXhfbnVtX2ZlYXR1cmVzPTIwKQpwbHQuc2hvdygpCmBgYAoKVGhlIGdsb2JhbCBmZWF0dXJlIHJhbmtpbmcgcmV2ZWFscyBzb21lIGhpZ2hseSByYW5rZWQgZmVhdHVyZXMgdG8gYmUgbWVhbmluZ2xlc3Mgb24gaXRzIG93bi4KRXNwZWNpYWxseSB0aGUgd29yZCBgaXRgLgpCdXQgYXMgZGlzY3Vzc2VkIGVhcmxpZXIgd2Ugc2hvdWxkbid0IG92ZXItaW50ZXJwcmV0IHRoZSByYW5rcyB3aXRob3V0IGEgcHJvcGVyIGV4cGxhbmF0aW9uIG1vZGVsaW5nLgoKU2luY2UgYHNoYXAuVHJlZUV4cGxhaW5lcmAgaXMgY3VzdG9taXplZCBmb3IgR0JUIGZvciBzcGVlZCwKd2UgY2FuIGZlZWQgaW4gYWxsIHRlc3RpbmcgZXhhbXBsZXMgdG8gY2FsY3VsYXRlIGFsbCBzaGFwIHZhbHVlcyBhdCBvbmNlLgoKYGBge3B5dGhvbiBzaGFwX2ltZGJfbGdifQppbXBvcnQgc2hhcAoKIyBTcGFyc2UgbWF0cml4IGlzIHN1cHBvcnRlZCBieSBzaGFwIGZvciBsaWdodGdibSBtb2RlbHMuCmltZGJfbGdiX2V4cGxhaW5lciA9IHNoYXAuVHJlZUV4cGxhaW5lcihpbWRiX2JzdCkKaW1kYl9sZ2Jfc2hhcF92YWx1ZXMgPSBpbWRiX2xnYl9leHBsYWluZXIuc2hhcF92YWx1ZXMoaW1kYl9YX3Rlc3QpCgpkZWYgaW1kYl9sZ2Jfc2hhcF9wbG90KHRlc3RfaWQsIG1hdHBsb3RsaWI9VHJ1ZSk6CiAgc2hhcF9wbHQgPSBzaGFwLmZvcmNlX3Bsb3QoCiAgICBpbWRiX2xnYl9leHBsYWluZXIuZXhwZWN0ZWRfdmFsdWVbMV0sCiAgICBpbWRiX2xnYl9zaGFwX3ZhbHVlc1sxXVt0ZXN0X2lkLDpdLAogICAgaW1kYl9YX3Rlc3RbdGVzdF9pZCw6XS50b2FycmF5KCksICAjIFdlIHN0aWxsIG5lZWQgYSBkZW5zZSBtYXRyaXggaGVyZS4KICAgIGZlYXR1cmVfbmFtZXM9c29ydGVkX3ZvY2FiLAogICAgbWF0cGxvdGxpYj1tYXRwbG90bGliCiAgKQogIHJldHVybiBzaGFwX3BsdApgYGAKCiMjIyMgR2xvYmFsIEltcG9ydGFuY2Ugey19CgpPbmUgYWR2YW50YWdlIG9mIGBzaGFwYCBvbiBHQlQgbW9kZWxzIGlzIHRoZSBjYXBhYmlsaXR5IG9mIHRyYXZlcnNlIHRocm91Z2ggYWxsIHRoZSB0ZXN0aW5nIGV4YW1wbGVzIGR1ZSB0byBpdHMgZWZmaWNpZW5jeS4KU28gd2UgY2FuIGJhc2VkIG9uIGFsbCB0aGUgcmVzdWx0aW5nIHNoYXAgdmFsdWVzIHRvIGRlcml2ZSBhIGdsb2JhbCBmZWF0dXJlIGltcG9ydGFuY2UganVkZ2VkIGJ5IHRoZWlyIGF2ZXJhZ2Ugc2hhcCB2YWx1ZXMgKGNvbnRyaWJ1dGlvbnMpLgpOb3RlIHRoYXQgdGhpcyBpcyBkaWZmZXJlbnQgZnJvbSB0aGUgbG9zcy9pbXB1cml0eSBvciBzcGxpdCB0aW1lLWJhc2VkIGZlYXR1cmUgcmFua2luZyBkZXJpdmVkIGZyb20gUkYvR0JUICpkdXJpbmcgdHJhaW5pbmcqLgpJdCBpcyBhbiBhZ2dyZWdhdGlvbiBmcm9tIGFsbCBsb2NhbCBwcmVkaWN0aW9uIGV4cGxhbmF0aW9ucyAoY29udHJpYnV0aW9ucykgKmR1cmluZyB0ZXN0aW5nIGRhdGEgaW5mZXJlbmNlKi4KCmBgYHtweXRob24gc2hhcF9pbWRiX2xnYl9mZWF0X2ltcH0Kc2hhcC5zdW1tYXJ5X3Bsb3QoaW1kYl9sZ2Jfc2hhcF92YWx1ZXMsIGltZGJfWF90ZXN0LCBmZWF0dXJlX25hbWVzPXNvcnRlZF92b2NhYiwKICAgICAgICAgICAgICAgICAgcGxvdF90eXBlPSJiYXIiLCBtYXhfZGlzcGxheT0yMCwgc2hvdz1GYWxzZSwgcGxvdF9zaXplPS4yNSkKcGx0LnNob3coKQpgYGAKCkFzIHdlIGNhbiBzZWUsCnRoZSByYW5raW5nIGJhc2VkIG9uIHNoYXAgdmFsdWVzIGZvciB0ZXN0aW5nIHNldCB3aWxsIGJlIGluIGdlbmVyYWwgZGlmZmVyZW50IGZyb20gdGhlIHJhbmtpbmcgYmFzZWQgb24gdHJhaW5pbmcgc3BsaXQuCkFuZCBpdCBpcyBtb3JlICppbnRlcnByZXRhYmxlKjoKRmVhdHVyZXMgd2l0aCBoaWdoZXIgcmFuayBsaXRlcmFsbHkgaGF2ZSBhdmVyYWdlbHkgaGlnaGVyIGltcGFjdCBvbiB0aGUgdGVzdGluZyBkYXRhc2V0LgpBbHNvIHRoZSByYW5raW5nIGNhbiBiZSBjb25kaXRpb25lZCBvbiBsYWJlbHMuCgojIyMjIExvY2FsIEV4cGxhbmF0aW9uIHstfQoKVGhlIG1vc3QgaW1wb3J0YW50IGFwcGxpY2F0aW9uIG9mIGBzaGFwYCBzdGlsbCBsaWVzIG9uIGluc3RhbmNlLWxldmVsIGV4cGxhbmF0aW9uLgpXZSBzdGljayB0byB0aGUgcHJldmlvdXMgdHdvIHJldmlld3MuCkZvciB0aGUgcmV2aWV3IHRoYXQgUkYgY29ycmVjdGx5IGxhYmVsIHBvc2l0aXZlLAp3ZSBoYXZlIHRoZSBgc2hhcGAgZXhwbGFuYXRpb24gd2l0aCB0aGUgZm9sbG93aW5nIHZpc3VhbGl6YXRpb246CgpgYGB7cHl0aG9uIHNoYXBfaW1kYl9sZ2JfdHBfZXhwfQppbWRiX2xnYl9zaGFwX3Bsb3QoaW1kYl9yZl90cF9pZHhbMF0pCmBgYAoKTm90ZSB0aGF0IGJ5IGRlZmF1bHQgYHNoYXBgIGZvciBgbGlnaHRnYm1gIHNob3dzIGxvZy1vZGRzIHJhdGhlciB0aGFuIHByb2JhYmlsaXR5IGluIHRoZSBwbG90LgpTbyBhIHBvc2l0aXZlIHZhbHVlIGluZGljYXRlcyBhIHBvc2l0aXZlIHByZWRpY3Rpb24sCm90aGVyd2lzZSBuZWdhdGl2ZS4KClRvIHZlcmlmeSB0aGlzOgoKYGBge3B5dGhvbiB2ZXJpZnlfbG9nX29kZHN9CmRlZiB0b19sb2dfb2RkcyhwKToKICByZXR1cm4gbnAubG9nKHAgLyAoMSAtIHApKQoKZGVmIHRvX3AobG9nX29kZHMpOgogIHJldHVybiBucC5leHAobG9nX29kZHMpLygxICsgbnAuZXhwKGxvZ19vZGRzKSkKCiMgVGFrZSB0aGUgZmlyc3QgdHJ1ZSBwb3NpdGl2ZSB0byBleGFtaW5lOgpwID0gaW1kYl9ic3QucHJlZGljdChpbWRiX1hfdGVzdFtpbWRiX3JmX3RwX2lkeFswXSw6XS50b2FycmF5KCkpCnByaW50KHApCnByaW50KHRvX2xvZ19vZGRzKHApKSAgIyBUaGlzIGlzIHRoZSByZXBvcnRlZCBudW1iZXIgb24gdGhlIGRlZmF1bHQgc2hhcCBwbG90LgpgYGAKCkZvciBhbnkgZ2l2ZW4gcHJlZGljdGlvbiwKdGhlIHNoYXAgdmFsdWVzIG9mIGFsbCBmZWF0dXJlcyBzaG91bGQgc3VtIHVwIHRvIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHByZWRpY3RlZCBsb2ctb2RkcyBhbmQgdGhlIGV4cGVjdGVkIGxvZy1vZGRzLgpUbyB2ZXJpZnkgdGhpcyBvbiB0aGUgc3BlY2lmaWMgcG9zaXRpdmUgZXhhbXBsZToKCmBgYHtweXRob24gdmVyaWZ5X3NoYXBfdmFsdWVzfQpleHBlY3RlZF9sb2dfb2RkcyA9IGltZGJfbGdiX2V4cGxhaW5lci5leHBlY3RlZF92YWx1ZVsxXQpwcmVkaWN0ZWRfbG9nX29kZHMgPSB0b19sb2dfb2RkcyhwKQoKcHJpbnQocHJlZGljdGVkX2xvZ19vZGRzIC0gZXhwZWN0ZWRfbG9nX29kZHMpICAjIFRoZSBkaWZmZXJlbmNlLgoKc2hhcF92ID0gcGQuRGF0YUZyYW1lKHsKICAidG9rZW4iOiBzb3J0ZWRfdm9jYWIsCiAgInNoYXBfdmFsdWUiOiBpbWRiX2xnYl9zaGFwX3ZhbHVlc1sxXVtpbWRiX3JmX3RwX2lkeFswXSw6XSwKICAidGZpZGYiOiBucC5zcXVlZXplKGltZGJfWF90ZXN0W2ltZGJfcmZfdHBfaWR4WzBdXS50b2FycmF5KCkpCn0pCnNoYXBfdiA9IHNoYXBfdi5zb3J0X3ZhbHVlcygic2hhcF92YWx1ZSIsIGFzY2VuZGluZz1GYWxzZSkKcHJpbnQoc2hhcF92KSAgIyBTaGFwIHZhbHVlcyBvZiBhbGwgZmVhdHVyZXMgZm9yIHRoZSBleGFtcGxlLgoKcHJpbnQoc2hhcF92LnNoYXBfdmFsdWUuc3VtKCkpICAjIFRoZSBzdW0gb2Ygc2hhcCB2YWx1ZXMuCmBgYAoKRnJvbSB0aGUgZW50aXJlIHNoYXAgdmFsdWVzIHdlIGNhbiBrbm93IGZvciBleGFtcGxlIHRoYXQgdGhlIGFic2VuY2Ugb2YgYGdyZWF0YCBjb250cmlidXRlcyBuZWdhdGl2ZWx5LAphbmQgdGhlIHByZXNlbmNlIG9mIGBsb3ZlYCBjb250cmlidXRlcyBwb3NpdGl2ZWx5LAp0byB0aGUgZmluYWwgcHJlZGljdGlvbi4KCmBgYHtweXRob24gc2hhcF9pbWRiX2xnYl9mcF9leHB9CmltZGJfbGdiX3NoYXBfcGxvdChpbWRiX3JmX2ZwX2lkeFswXSkKYGBgCgpGb3IgdGhlIGZhbHNlIHBvc2l0aXZlIGNhc2UsCnNpbWlsYXIgdG8gUkYsCnRoZSB3b3JkIGBncmVhdGAgcGxheSBhIGJpZyByb2xlIGluIHNoYXBpbmcgdGhlIEdCVCBwcmVkaWN0aW9uIHRvd2FyZCBwb3NpdGl2ZS4KCiMjIyBFeHBsYWluIE5ldXJhbCBOZXRzIHdpdGggV29yZCBFbWJlZGRpbmdzCgpBcyBvZiBgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVZLSVtLSVkJylgIGBzaGFwLkRlZXBFeHBsYWluZXJgIGRvZXMgbm90IHlldCBzdXBwb3J0IFRGIDIuMC5eW2h0dHBzOi8vZ2l0aHViLmNvbS9zbHVuZGJlcmcvc2hhcC9pc3N1ZXMvODUwLl0KQW5kIGBzaGFwLkdyYWRpZW50RXhwbGFpbmVyYCBpcyBub3Qgd2VsbCBkb2N1bWVudGVkIHlldCBmb3IgVEYgMi4wLgpTbyB3ZSB3aWxsIHVzZSB0aGUgYHNoYXAuS2VybmVsRXhwbGFpbmVyYCB3aGljaCBpcyBhIGltcGxlbWVudGF0aW9uLWFnbm9zdGljIGV4cGxhaW5lciBpbiBgc2hhcGAuClRoZSBjb21wcm9taXNlIGlzIHRoYXQgaXQgd2lsbCBydW4gdmVyeSBzbG93IGZvciBlYWNoIHByZWRpY3Rpb24uCgpgYGB7cHl0aG9uIHNoYXBfa2VybmVsX2ltZGJfbm59CmltZGJfZXhwX2luZCA9IG5wLmFycmF5KFtpbWRiX3JmX3RwX2lkeFswXSwgaW1kYl9yZl9mcF9pZHhbMF1dKQojIEtlcm5lbEV4cGxhaW5lci4KZGVmIG1tKFgpOgogIHJldHVybiBpbWRiX3RyLnByZWRpY3RfcHJvYmEoWClbOiwxXQoKaW1kYl9ubl9zaGFwX2V4cGxhaW5lciA9IHNoYXAuS2VybmVsRXhwbGFpbmVyKG1tLCBzZXFfdHJhaW5fcGFkZGVkWzoxMDBdKQojIFRoaXMgaXMgVkVSWSBzbG93Li4uCiNpbWRiX25uX2tlcm5lbF9zaGFwX3ZhbHVlcyA9IGltZGJfbm5fc2hhcF9leHBsYWluZXIuc2hhcF92YWx1ZXMoc2VxX3Rlc3RfcGFkZGVkW2ltZGJfZXhwX2luZF0pCiMgVE9ETzoKIyBDb250cmlidXRpb24gaXMgYXR0cmlidXRlZCB0byBvcmlnaW5hbCBzZXF1ZW5jZSBpbnB1dC4KIyBJbiBvcmRlciB0byBtYWtlIGV4cGxhbmF0aW9uIHJlYWRhYmxlLAojIHdlIG5lZWQgdG8gbWFwIGVhY2ggcG9zaXRpb24gdG8gb3JpZ2luYWwgd29yZCBpZCB0aGVuIHRvIHdvcmQuCmBgYAoKYGBgcHl0aG9uCiMgVE9ETzogTWFramUgc3VyZSBldmVyeXRoaW5nIHdvcmtzIGhlcmUuCgojIHNoYXAgZG9lcyBub3Qgc3VwcG9ydCBrZXJhcyBtb2RlbCBpbiBzY2lraXQtbGVhcm4gd3JhcHBlci4KIyBMZXQncyByZS1idWlsZCB0aGUgbW9kZWwgYW5kIHJldGFpbiBpdHMgU2VxdWVudGFsIGNsYXNzLgpkbF9tb2RlbCA9IG1vZGVsX2ZuKCkKbWV0cmljcyA9IGRsX21vZGVsLmZpdCgKICB4PXNlcV90cmFpbl9wYWRkZWQsIHk9aW1kYl95X3RyYWluLAogIGJhdGNoX3NpemU9MjU2LCBlcG9jaHM9MjAsCiAgdmFsaWRhdGlvbl9kYXRhPShzZXFfdGVzdF9wYWRkZWQsIGltZGJfeV90ZXN0KSwKICB2YWxpZGF0aW9uX3N0ZXBzPTIwLAogIGNhbGxiYWNrcz1bCiAgICB0Zi5rZXJhcy5jYWxsYmFja3MuRWFybHlTdG9wcGluZyhtb25pdG9yPSJ2YWxfbG9zcyIsIHBhdGllbmNlPTIpLAogICAgdGYua2VyYXMuY2FsbGJhY2tzLk1vZGVsQ2hlY2twb2ludCh0cl9tb2RlbF9maWxlLCBtb25pdG9yPSJ2YWxfbG9zcyIsIHNhdmVfYmVzdF9vbmx5PVRydWUpCiAgXSwKICB2ZXJib3NlPTApCgojIERlZXBFeHBsYWluZXIuCmRsX3NoYXBfZXhwbGFpbmVyID0gc2hhcC5EZWVwRXhwbGFpbmVyKGRsX21vZGVsLCBzZXFfdHJhaW5fcGFkZGVkKSAgIyBXb250JyB3b3JrLgoKIyBHcmFkaWVudEV4cGxhaW5lci4KaW1kYl9ubl9zaGFwX2V4cGxhaW5lciA9IHNoYXAuR3JhZGllbnRFeHBsYWluZXIoZGxfbW9kZWwsIHNlcV90cmFpbl9wYWRkZWRbOjEwMF0pCgppbWRiX25uX3NoYXBfZXhwbGFpbmVyID0gc2hhcC5HcmFkaWVudEV4cGxhaW5lcigKICAoaW1kYl90ci5sYXllcnNbMF0uaW5wdXQsIGltZGJfdHIubGF5ZXJzWy0xXS5vdXRwdXQpLCAgIyBOb3Qgd29ya2luZyBmb3IgVEYgMi4wLgogIHNlcV90cmFpbl9wYWRkZWRbOjEwMF0pCmltZGJfbm5fc2hhcF9leHBsYWluZXIuc2hhcF92YWx1ZXMoc2VxX3Rlc3RfcGFkZGVkWzozXSkgICMgRXJyb3IgaGVyZS4KYGBgCgojIyBPbiBUYWJ1bGFyIERhdGEgQ2xhc3NpZmllcgoKV2UgZG8gdGhlIHNhbWUgZXhlcmNpc2Ugb24gdGhlIHRhYnVsYXIgZGF0YXNldCBwcmV2aW91c2x5IGV4cGxhaW5lZCBieSBgbGltZWAuCgojIyMgRXhwbGFpbiBSYW5kb20gRm9yZXN0CgpgYGB7cHl0aG9uIHNoYXBfdWNpaGRfcmZ9CnVjaWhkX3JmX2V4cGxhaW5lciA9IHNoYXAuVHJlZUV4cGxhaW5lcih1Y2loZF9yZikKdWNpaGRfcmZfc2hhcF92YWx1ZXMgPSB1Y2loZF9yZl9leHBsYWluZXIuc2hhcF92YWx1ZXModWNpaGRfWF90ZXN0KQoKZGVmIHVjaWhkX3JmX3NoYXBfcGxvdCh0ZXN0X2lkLCBtYXRwbG90bGliPVRydWUpOgogIHNoYXBfcGx0ID0gc2hhcC5mb3JjZV9wbG90KAogICAgdWNpaGRfcmZfZXhwbGFpbmVyLmV4cGVjdGVkX3ZhbHVlWzFdLAogICAgdWNpaGRfcmZfc2hhcF92YWx1ZXNbMV1bdGVzdF9pZCw6XSwKICAgIHVjaWhkX1hfdGVzdC5pbG9jW1t0ZXN0X2lkXV0sCiAgICBtYXRwbG90bGliPW1hdHBsb3RsaWIKICApCiAgcmV0dXJuIHNoYXBfcGx0CmBgYAoKIyMjIyBHbG9iYWwgRmVhdHVyZSBJbXBvcnRhbmNlIHstfQoKRnJvbSB0aGUgZ2xvYmFsIHJhbmtpbmcgd2UgY2FuIGNvbmZpcm0gdGhhdCB2YXJpYWJsZSBgY2FgIGlzIGRlZmluaXRlbHkgYW4gaW5mbHVlbnRpYWwgZmVhdHVyZS4KCiMjIyMjIFNwbGl0LXRpbWUtYmFzZWQgZmVhdHVyZSByYW5raW5nIHstfQoKYGBge3B5dGhvbiB1Y2loZF9yZl9mZWF0X2ltcH0KdWNpaGRfcmZfZmVhdF9pbXAgPSBwZC5TZXJpZXModWNpaGRfcmYuZmVhdHVyZV9pbXBvcnRhbmNlc18sIGluZGV4PXVjaWhkX1hfdHJhaW4uY29sdW1ucykuc29ydF92YWx1ZXMoKQpheCA9IHVjaWhkX3JmX2ZlYXRfaW1wLnRhaWwoMTApLnBsb3Qoa2luZD0iYmFyaCIpCnBsdC5zaG93KCkgICMgVE9ETzogQWRqdXN0IHBsb3Qgc2l6ZS4KYGBgCgojIyMjIyBTaGFwIHZhbHVlIGZlYXR1cmUgcmFua2luZyB7LX0KCmBgYHtweXRob24gc2hhcF91Y2loZF9yZl9mZWF0X2ltcH0Kc2hhcC5zdW1tYXJ5X3Bsb3QodWNpaGRfcmZfc2hhcF92YWx1ZXMsIHVjaWhkX1hfdGVzdCwKICAgICAgICAgICAgICAgICAgcGxvdF90eXBlPSJiYXIiLCBtYXhfZGlzcGxheT0xMCwgc2hvdz1GYWxzZSwgcGxvdF9zaXplPS4yNSkKcGx0LnNob3coKQpgYGAKCiMjIyMjIEZlYXR1cmUgSW50ZXJhY3Rpb24gey19CgpXZSBjYW4gcGxvdCAqcGFydGlhbCBkZXBlbmRlbmN5KiBiYXNlZCBvbiBzaGFwIHZhbHVlcyBvZiB0d28gZmVhdHVyZXMgb3ZlciB0aGUgZW50aXJlIHRlc3RpbmcgZGF0YXNldC4KRm9yIGV4YW1wbGUsCmJ5IGtub3dpbmcgdGhhdCBgY2FgIGlzIGltcG9ydGFudCwKd2UnZCBsaWtlIHRvIGZ1cnRoZXIga25vdyBob3cgYGFnZWAgY2FuIGltcGFjdCB0aGUgY29udHJpYnV0aW9uIG9mIGBjYWAgYWNyb3NzIGRpZmZlcmVudCBleGFtcGxlcy4KCmBgYHtweXRob24gc2hhcF9yZl9kZXBfcGxvdF9hZ2VfY2F9CnNoYXAuZGVwZW5kZW5jZV9wbG90KCJhZ2UiLCB1Y2loZF9yZl9zaGFwX3ZhbHVlc1sxXSwgdWNpaGRfWF90ZXN0LCBpbnRlcmFjdGlvbl9pbmRleD0iY2EiKQpgYGAKClRoZSByZXN1bHQgc3VnZ2VzdHMgdHdvIHRoaW5nczoKCjEuIFRoZSBtb2RlbCB3aWxsIHByZWRpY3QgaGlnaGVyIHJpc2sgZm9yIG9sZGVyIHBlb3BsZQoyLiBgY2FgIGhhcyBsZXNzIGltcGFjdCBmb3IgeW9uZ2VyIHBlb3BsZQoKQm90aCBjYW4gYmUgZXhhbWluZWQgYnkgZG9tYWluLWV4cGVydHMgdG8gc2VlIGlmIHRoZSBtb2RlbCBpcyBsZWFybmluZyB0aGUgY29ycmVjdCBwYXR0ZXJuIHRoYXQgd2UgZXhwZWN0ZWQgb3IgYXQgbGVhc3QgdGhhdCB3ZSBjYW4gcmVhc29uLgoKIyMjIyBMb2NhbCBFeHBsYW5hdGlvbiB7LX0KCk5vdGUgdGhhdCBmb3IgYHNjaWtpdC1sZWFybmAgUkYgbW9kZWwgYnkgZGVmYXVsdCBgc2hhcGAgcmVwb3J0cyBwcm9iYWJpbGl0eSBpbnN0ZWFkIG9mIGxvZy1vZGRzLgpTdWNoIGJlaGF2aW9yIGRpZmZlcmVuY2UgcmVzdWx0cyBmcm9tIHRoZSBvcHRpbWl6YXRpb24gY3VzdG9taXplZCBmb3IgR0JUIG1vZGVsIGZhbWlseS4KCmBgYHtweXRob24gc2hhcF91Y2loZF9yZl90cF9leHB9CiMgVGhlIHRydWUgcG9zaXRpdmUgY2FzZSBpbiBSRi4KdWNpaGRfcmZfc2hhcF9wbG90KHVjaWhkX3JmX3RwX2lkeFswXSkKYGBgCgpgYGB7cHl0aG9uIHNoYXBfdWNpaGRfcmZfZnBfZXhwfQojIFRoZSBmYWxzZSBwb3NpdGl2ZSBjYXNlIGluIFJGLgp1Y2loZF9yZl9zaGFwX3Bsb3QodWNpaGRfcmZfZnBfaWR4WzBdKQpgYGAKCiMjIyBFeHBsYWluIEdyYWRpZW50IEJvb3N0aW5nIFRyZWVzCgpGb3IgR0JUIHdlIGZlZWQgdGhlIG1vZGVsIHRoYXQgaXMgb3B0aW1pemVkLAp3aGVyZSBjYXRlZ29yaWNhbHMgYXJlIGVuY29kZWQgaW50ZXJuYWxseSB3aXRob3V0IGV4cGxpY2l0IG9uZS1ob3QgZW5jb2RpbmcuCgpgYGB7cHl0aG9uIHNoYXBfdWNpaGRfbGdifQp1Y2loZF9sZ2JfZXhwbGFpbmVyID0gc2hhcC5UcmVlRXhwbGFpbmVyKHVjaWhkX2JzdF8yKQp1Y2loZF9sZ2Jfc2hhcF92YWx1ZXMgPSB1Y2loZF9sZ2JfZXhwbGFpbmVyLnNoYXBfdmFsdWVzKHVjaWhkX3Rlc3QuZHJvcCgibGFiZWwiLCBheGlzPTEpKQoKZGVmIHVjaWhkX2xnYl9zaGFwX3Bsb3QodGVzdF9pZCwgbWF0cGxvdGxpYj1UcnVlKToKICBzaGFwX3BsdCA9IHNoYXAuZm9yY2VfcGxvdCgKICAgIHVjaWhkX2xnYl9leHBsYWluZXIuZXhwZWN0ZWRfdmFsdWVbMV0sCiAgICB1Y2loZF9sZ2Jfc2hhcF92YWx1ZXNbMV1bdGVzdF9pZCw6XSwKICAgIHVjaWhkX3Rlc3QuaWxvY1tbdGVzdF9pZF1dLmRyb3AoImxhYmVsIiwgYXhpcz0xKSwKICAgIG1hdHBsb3RsaWI9bWF0cGxvdGxpYgogICkKICByZXR1cm4gc2hhcF9wbHQKYGBgCgojIyMjIEdsb2JhbCBGZWF0dXJlIEltcG9ydGFuY2Ugey19CgojIyMjIyBTcGxpdC10aW1lLWJhc2VkIGZlYXR1cmUgcmFua2luZyB7LX0KCmBgYHtweXRob24gdWNpaGRfbGdiX2ZlYXRfaW1wfQpheCA9IGxnYi5wbG90X2ltcG9ydGFuY2UodWNpaGRfYnN0XzIsIG1heF9udW1fZmVhdHVyZXM9MTApCnBsdC5zaG93KCkKYGBgCgojIyMjIyBTaGFwIHZhbHVlIGZlYXR1cmUgcmFua2luZyB7LX0KCmBgYHtweXRob24gc2hhcF91Y2loZF9sZ2JfZmVhdF9pbXB9CnNoYXAuc3VtbWFyeV9wbG90KHVjaWhkX2xnYl9zaGFwX3ZhbHVlcywgdWNpaGRfdGVzdC5kcm9wKCJsYWJlbCIsIGF4aXM9MSksCiAgICAgICAgICAgICAgICAgIHBsb3RfdHlwZT0iYmFyIiwgbWF4X2Rpc3BsYXk9MTAsIHNob3c9RmFsc2UsIHBsb3Rfc2l6ZT0uMjUpCnBsdC5zaG93KCkKYGBgCgojIyMjIyBGZWF0dXJlIEludGVyYWN0aW9uIHstfQoKYGBge3B5dGhvbiBzaGFwX2xnYl9kZXBfcGxvdF9hZ2VfY2F9CnNoYXAuZGVwZW5kZW5jZV9wbG90KCJhZ2UiLCB1Y2loZF9sZ2Jfc2hhcF92YWx1ZXNbMV0sCiAgICAgICAgICAgICAgICAgICAgIHVjaWhkX3Rlc3QuZHJvcCgibGFiZWwiLCBheGlzPTEpLCBpbnRlcmFjdGlvbl9pbmRleD0iY2EiKQpgYGAKCiMjIyMgTG9jYWwgRXhwbGFuYXRpb24gey19CgpgYGB7cHl0aG9uIHNoYXBfdWNpaGRfbGdiX3RwX2V4cH0KdWNpaGRfbGdiX3NoYXBfcGxvdCh1Y2loZF9yZl90cF9pZHhbMF0pCmBgYAoKYGBge3B5dGhvbiBzaGFwX3VjaWhkX2xnYl9mcF9leHB9CnVjaWhkX2xnYl9zaGFwX3Bsb3QodWNpaGRfcmZfZnBfaWR4WzBdKQpgYGAKCiMjIyBUaGUgSW1wYWN0IG9mIE9uZS1Ib3QgRW5jb2RpbmcgT24gRXhwbGFuYXRpb24KCkFzIG9uZSBtYXkgbm93IHJlYWxpemUsCmJ5IGV4cGxpY2l0bHkgb25lLWhvdC1lbmNvZGUgdGhlIGNhdGVnb3JpY2FsIGZlYXR1cmVzIHdlIGVzc2VudGlhbGx5IHNwbGl0IHRoZW0gaW50byBkaWZmZXJlbnQgZmVhdHVyZXMgaW4gdGhlaXIgaW50ZXJwcmV0YWJsZSByZXByZXNlbnRhdGlvbi4KVGhpcyBjYW4gYmUgZWl0aGVyIGdvb2Qgb3IgYmFkLCBkZXBlbmRpbmcgb24gdGhlIGFjdHVhbCB1c2UgY2FzZS4KRnJvbSB0aGlzIHBhcnRpY3VsYXIgYXNwZWN0IGxpYmFyeSBzdWNoIGFzIGBsaWdodGdibWAgcHJvdmlkZXMgdGhlIGZsZXhpYmlsaXR5IHRvIGFsbG93IHVzIGNob29zZSB3aGV0aGVyIHRvIGRvIHRoZSBvbmUtaG90IGVuY29kaW5nIG9yIG5vdC4KU28gdGhlIHdheSB3ZSB3YW50IHRvIGNvbnN0cnVjdCB0aGUgZXhwbGFuYXRpb24gbW9kZWwgbWF5IHdlbGwgYWZmZWN0IG91ciBpbXBsZW1lbnRhdGlvbiBvZiB0aGUgb3JpZ2luYWwgbW9kZWwuCgojIyBPbiBJbWFnZSBDbGFzc2lmaWVyCgoqKlRPRE86IFVzZSBhIHByZS10cmFpbmVkIG1vZGVsPyoqCgojIEV4cGxhaW5hYmxlIEJvb3N0aW5nIE1hY2hpbmUKCkBub3JpMjAxOWludGVycHJldG1sIHB1Ymxpc2ggdGhlIG9wZW4gc291cmNlIHBhY2thZ2UgYGludGVycHJldGAgZm9yIGEgZmFzdCBpbXBsZW1lbnRhdGlvbiBvZiAqKkdlbmVyYWxpemVkIEFkZGl0aXZlIE1vZGVscyB3aXRoIFBhaXJ3aXNlIEludGVyYWN0aW9ucywgb3IgR0E8c3VwPjI8L3N1cD5NKiogKEBsb3UyMDEzYWNjdXJhdGUpLgpBcyBvZiBgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVZLSVtLSVkJylgLCBgaW50ZXJwcmV0YCBpcyBzdGlsbCBpbiBpdHMgYWxwaGEgcmVsZWFzZSB3aXRoIGxpbWl0ZWQgZG9jdW1lbnRhdGlvbi4KVGhlIGxpYnJhcnkgY29udGFpbnMgdHdvIGdyb3VwcyBvZiBtb2RlbGluZyBmcmFtZXdvcmtzOgoKKyBgZ2xhc3Nib3hgOiBleHBsYW5hYmxlIG1hY2hpbmUgbGVhcm5pbmcgbW9kZWxzCisgYGJsYWNrYm94YDogbWFjaGluZSBsZWFybmluZyBleHBsYW5hdGlvbiBtb2RlbHMgKHN1Y2ggYXMgTElNRSBhbmQgU0hBUCkKCldlJ3ZlIGFscmVhZHkgY292ZXJlZCB0aGUgbWFpbnN0cmVhbSBhcHByb2FjaCBpbiB0aGUgc2Vjb25kIGdyb3VwLAppLmUuLAptb2RlbHMgdGhhdCBhcHByb3hpbWF0ZSAobG9jYWxseSkgdGhlIG9yaWdpbmFsIG1vZGVsIChzdXBwb3NlZCB0byBiZSBhIGJsYWNrYm94KSBmb3IgYmV0dGVyIGV4cGxhaW5hYmlsaXR5LgpUaGUgbW9yZSBpbnRlcmVzdGluZyBwYXJ0IG9mIGBpbnRlcnByZXRgIGlzIHRvIGJyaW5nIGFib3V0IGFub3RoZXIgdHlwZSBvZiBtb2RlbCB0aGF0IGlzIHJlYWRpbHkgaW50ZXJwcmV0YWJsZSBmcm9tIGl0cyB2ZXJ5IG9yaWdpbiwKYW5kIHlldCBzdGlsbCBjb21wZXRpdGl2ZWx5IGFjY3VyYXRlOgoqKnRoZSBFeHBsYWluYWJsZSBCb29zdGluZyBNYWNoaW5lKiosIG9yIEVCTS4KCkVCTSBpcyBhbiBhZGRpdGl2ZSBtb2RlbCBvZiB0aGUgZm9ybToKCiQkCmcoRSh5KSkgPSBcYmV0YV8wICsgXHN1bSBmX2ogKHhfaikgKyBcc3VtIGZfe2lqfSh4X2ksIHhfaiksCiQkCgp3aGVyZSAkZyhcY2RvdCkkIGlzIGEgbGluayBmdW5jdGlvbiAoc2lnbW9pZCBmb3IgYmluYXJ5IGNsYXNzaWZpY2F0aW9uLCBmb3IgYW4gZXhhbXBsZSksCiRmX2okIGlzIHRoZSAqZmVhdHVyZSBmdW5jdGlvbiogZm9yIHRoZSAkaiQtdGggZmVhdHVyZSwKbGVhcm5lZCBieSBhIGdyYWRpZW50IGJvb3N0aW5nIG1hY2hpbmUgd2l0aCBvbmx5IHRoYXQgZmVhdHVyZSBhdCBhIHRpbWUgYW5kIGluIGEgcm91bmQtcm9iaW4gZmFzaGlvbiBmb3IgYWxsIGZlYXR1cmVzLgokZl97aWp9JCBpcyBhICpwYWlyd2lzZSBpbnRlcmFjdGlvbiogZmVhdHVyZSBmdW5jdGlvbiB0byBmdXJ0aGVyIGJvb3N0IHRoZSBhY2N1cmFjeSBvZiB0aGUgbW9kZWwgd2hpbGUgcmVtYWluIGludGVycHJldGFiaWxpdHkuCgpUaGUgbW9kZWwgaXMgaW50ZXJwcmV0YWJsZSBzaW5jZSB0aGUgY29udHJpYnV0aW9uIG9mIGFueSBpbmRpdmlkdWFsIGZlYXR1cmUgY2FuIGJlIGRpcmVjdGx5IHF1YW50aWZpZWQgYnkgdGhlaXIgY29ycmVzcG9uZGluZyBmZWF0dXJlIGZ1bmN0aW9uICRmX2okLgpTdWNoIGV4cGxhbmF0aW9uIGNhbiBleHRlbmQgdXAgdG8gcGFpcndpc2UgaW50ZXJhY3Rpb24gaWYgcGFpcndpc2UgZmVhdHVyZSBmdW5jdGlvbnMgYXJlIGFsc28gZXN0aW1hdGVkLgoKKipUT0RPOiBIb3cgdG8gZGV0ZWN0IHBhaXJ3aXNlIGludGVyYWN0aW9uPyBCcmllZiB0aGUgRkFTVCBhbGdvcml0aG0uKioKCiMjIE9uIFRleHQvSW1hZ2UgRGF0YQoKRUJNIGlzIG5vdCBlZmZpY2llbnQgZm9yIHRleHQgZGF0YXNldC4KRHVlIHRvIHRoZSBhbGdvcml0aG0ncyBkZXNpZ24gaXQgd2lsbCBydW4gdG9vIGxvbmcgZm9yIGJhZy1vZi13b3JkcyBtb2RlbCBzaW5jZSB0aGVyZSBhcmUgdG9vIG1hbnkgZmVhdHVyZSBmdW5jdGlvbnMgdG8gZXN0aW1hdGUuCklmIHdlIGZpdCBhIEVCTSB3aXRoIHRoZSBtb3ZpZSByZXZpZXcgZGF0YXNldCwKZXZlbiBpZiBub3QgYSBsYXJnZSBkYXRhc2V0LAp3ZSB3aWxsIGVuY291bnRlciBPT00gKG91dC1vZi1tZW1vcnkpIGlzc3VlLgpBcyBhIHJlc3VsdCwKd2Ugd2lsbCBza2lwIHRoZSBkaXNjdXNzaW9uIG9mIEVCTSBvbiBhIHRleHQgY2xhc3NpZmllci4KKFRoZSBzYW1lIHJlc3RyaWN0aW9uIGFwcGxpZXMgdG8gaW1hZ2UgZGF0YXNldC4pCgojIyBPbiBUYWJ1bGFyIERhdGEKCmBFeHBsYWluYWJsZUJvb3N0aW5nQ2xhc3NpZmllcmAgaGFzIGEgYHNjaWtpdC1sZWFybmAgZmFzaGlvbiBBUEkgYW5kIGhlbmNlIGlzIHN0cmFpZ2h0Zm9yd2FyZCB0byB1c2UuCgpgYGB7cHl0aG9uIHVjaWhkX2VibX0KZnJvbSBpbnRlcnByZXQuZ2xhc3Nib3ggaW1wb3J0IEV4cGxhaW5hYmxlQm9vc3RpbmdDbGFzc2lmaWVyCgp1Y2loZF9lYm0gPSBFeHBsYWluYWJsZUJvb3N0aW5nQ2xhc3NpZmllcigKICBuX2VzdGltYXRvcnM9MTYsIGZlYXR1cmVfbmFtZXM9dWNpaGRfMi5jb2x1bW5zLCBuX2pvYnM9MSkKXyA9IHVjaWhkX2VibS5maXQodWNpaGRfWF90cmFpbiwgdWNpaGRfeV90cmFpbikKCnVjaWhkX2VibV95aGF0ID0gdWNpaGRfZWJtLnByZWRpY3RfcHJvYmEodWNpaGRfWF90ZXN0KVs6LDFdCnVjaWhkX2VibV9wcmVkID0gKHVjaWhkX2VibV95aGF0ID4gLjUpLmFzdHlwZShpbnQpCgpwcmludChjbGFzc2lmaWNhdGlvbl9yZXBvcnQodWNpaGRfeV90ZXN0LCB1Y2loZF9lYm1fcHJlZCkpCnByaW50KHJvY19hdWNfc2NvcmUodWNpaGRfeV90ZXN0LCB1Y2loZF9lYm1feWhhdCkpCmBgYAoKVGhlIG1vZGVsIHBlcmZvcm1zIHZlcnkgd2VsbCBvbiB0aGUgaGVhcnQgZGlzZWFzZSBkYXRhc2V0LApvdXRwZXJmb3JtaW5nIGJvdGggUkYgYW5kIEdCVC4KCiMjIyBHbG9iYWwgRXhwbGFuYXRpb24KCmBpbnRlcnByZXRgIGNvbWVzIHdpdGggYSByaWNoIHNldCBvZiB2aXN1YWxpemF0aW9uIHRvb2xzICh3aXRoIFtgcGxvdGx5YF0oaHR0cHM6Ly9wbG90Lmx5LykgYXMgaXRzIGJhY2tlbmQpLgpNb2RlbCBleHBsYW5hdGlvbiBpcyBkaXZpZGVkIGludG8gdHdvIGdyb3VwczoKZ2xvYmFsIGFuZCBsb2NhbC4KCkZvciBnbG9iYWwgZXhwbGFuYXRpb24sCndlIGhhdmUgYWNjZXNzIHRvIGJvdGggZ2xvYmFsIGZlYXR1cmUgaW1wb3J0YW5jZSBhbmQgYSBwZXItZmVhdHVyZSBmZWF0dXJlIGNvbnRyaWJ1dGlvbiBzdGF0cy4KCmBgYHtweXRob24gdWNpaGRfZWJtX2dsb2JhbF9leHBsYWlufQp1Y2loZF9lYm1fZ2xvYmFsID0gdWNpaGRfZWJtLmV4cGxhaW5fZ2xvYmFsKCkKIyBBbGwgZmVhdHVyZSBpbmZvOgpwcmludCh1Y2loZF9lYm1fZ2xvYmFsLnNlbGVjdG9yKQoKIyBHbG9iYWwgZmVhdHVyZSBpbXBvcnRhbmNlLgp1Y2loZF9lYm1fZ2xvYmFsLnZpc3VhbGl6ZSgpLndyaXRlX2h0bWwoIi90bXAvdWNpaGRfZWJtX2ZlYXRfaW1wLmh0bWwiLCBpbmNsdWRlX3Bsb3RseWpzPUZhbHNlKQpgYGAKCmBgYHtweXRob24gdWNpaGRfZWJtX2dsb2JhbF9leHBsYWluX3Bsb3R9CiMgR2xvYmFsIGNvbnRyaWJ1dGlvbiBvbiBhZ2UuCmZpZCA9IHVjaWhkX2VibV9nbG9iYWwuc2VsZWN0b3IuTmFtZS50b2xpc3QoKS5pbmRleCgiYWdlIikKdWNpaGRfZWJtX2dsb2JhbC52aXN1YWxpemUoZmlkKS53cml0ZV9odG1sKCIvdG1wL3VjaWhkX2VibV9hZ2VfaW1wLmh0bWwiLCBpbmNsdWRlX3Bsb3RseWpzPUZhbHNlKQoKIyBHbG9iYWwgY29udHJpYnV0aW9uIG9uIHRyZXN0YnBzLgpmaWQgPSB1Y2loZF9lYm1fZ2xvYmFsLnNlbGVjdG9yLk5hbWUudG9saXN0KCkuaW5kZXgoInRyZXN0YnBzIikKdWNpaGRfZWJtX2dsb2JhbC52aXN1YWxpemUoZmlkKS53cml0ZV9odG1sKCIvdG1wL3VjaWhkX2VibV90cmVzdGJwc19pbXAuaHRtbCIsIGluY2x1ZGVfcGxvdGx5anM9RmFsc2UpCgojIEdsb2JhbCBjb250cmlidXRpb24gb24gc2V4LgpmaWQgPSB1Y2loZF9lYm1fZ2xvYmFsLnNlbGVjdG9yLk5hbWUudG9saXN0KCkuaW5kZXgoInNleF8wLjAiKQp1Y2loZF9lYm1fZ2xvYmFsLnZpc3VhbGl6ZShmaWQpLndyaXRlX2h0bWwoIi90bXAvdWNpaGRfZWJtX3NleF9pbXAuaHRtbCIsIGluY2x1ZGVfcGxvdGx5anM9RmFsc2UpCmBgYAoKIyMjIyBGZWF0dXJlIEltcG9ydGFuY2Ugey19CgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTCgiL3RtcC91Y2loZF9lYm1fZmVhdF9pbXAuaHRtbCIpCmBgYAoKIyMjIyBGZWF0dXJlIENvbnRyaWJ1dGlvbjogQWdlIHstfQoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwoIi90bXAvdWNpaGRfZWJtX2FnZV9pbXAuaHRtbCIpCmBgYAoKIyMjIyBGZWF0dXJlIENvbnRyaWJ1dGlvbjogUmVzdGluZyBCbG9vZCBQcmVzc3VyZSB7LX0KCmBgYHtyLCBlY2hvPUZBTFNFfQpodG1sdG9vbHM6OmluY2x1ZGVIVE1MKCIvdG1wL3VjaWhkX2VibV90cmVzdGJwc19pbXAuaHRtbCIpCmBgYAoKIyMjIyBGZWF0dXJlIENvbnRyaWJ1dGlvbjogR2VuZGVyIChGZW1hbGUpIHstfQoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwoIi90bXAvdWNpaGRfZWJtX3NleF9pbXAuaHRtbCIpCmBgYAoKIyMjIExvY2FsIEV4cGxhbmF0aW9uCgpNb3JlIGltcG9ydGFudGx5LAp3ZSBtdXN0IGJlIGFibGUgdG8gZXhwbGFpbiBhIHNwZWNpZmljIG1vZGVsIHByZWRpY3Rpb24gbG9jYWxseS4KVGhpcyBjYW4gYWxzbyBiZSBkb25lIGVhc2lseSB3aXRoIGEgY291cGxlIG9mIGxpbmVzOgoKYGBge3B5dGhvbiB1Y2loZF9lYm1fbG9jYWxfZXhwbGFpbn0KIyBFeHBsYWluIHRoZSBzYW1lIGluc3RhbmNlcyBwcmV2aW91c2x5IG9uIFJGLgp1Y2loZF9leHBfaW5kID0gbnAuYXJyYXkoW3VjaWhkX3JmX3RwX2lkeFswXSwgdWNpaGRfcmZfZnBfaWR4WzBdXSkKCiMgV2UgY2FuIGZlZWQgbXVsdGlwbGUgZXhhbXBsZXMgYXQgdGhlIHNhbWUgdGltZS4KdWNpaGRfZWJtX2xvY2FsID0gdWNpaGRfZWJtLmV4cGxhaW5fbG9jYWwoCiAgdWNpaGRfWF90ZXN0Lmlsb2NbdWNpaGRfZXhwX2luZCw6XSwgdWNpaGRfeV90ZXN0W3VjaWhkX2V4cF9pbmRdKQp1Y2loZF9lYm1fbG9jYWwudmlzdWFsaXplKDApLndyaXRlX2h0bWwoIi90bXAvdWNpaGRfZWJtX2V4cF90cC5odG1sIiwgaW5jbHVkZV9wbG90bHlqcz1GYWxzZSkKdWNpaGRfZWJtX2xvY2FsLnZpc3VhbGl6ZSgxKS53cml0ZV9odG1sKCIvdG1wL3VjaWhkX2VibV9leHBfZnAuaHRtbCIsIGluY2x1ZGVfcGxvdGx5anM9RmFsc2UpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwoIi90bXAvdWNpaGRfZWJtX2V4cF90cC5odG1sIikKYGBgCgpGb3IgdGhlIGZhbHNlIHBvc2l0aXZlIGNhc2UgbWFkZSBieSBib3RoIFJGIGFuZCBHQlQsCkVCTSBpcyBhYmxlIHRvIGNvcnJlY3RseSBwcmVkaWN0IHRoZSBuZWdhdGl2ZSBsYWJlbC4KV2Ugc3RpbGwgc2VlIGEgcG9zaXRpdmUgYGNhYCB2YWx1ZSBjb250cmlidXRlIGEgbG90IHRvd2FyZCBhIHBvc2l0aXZlIHByZWRpY3Rpb24sCndoaWxlIEVCTSBpcyBhYmxlIHRvIGFsc28gcGljayB1cCBzZXZlcmFsIG5lZ2F0aXZlIGZhY3RvcnMgdGhhdCBqb2ludGx5IG5lZ2F0ZSB0aGUgcG9zaXRpdmUgaW1wYWN0LAplbmRpbmcgdXAgd2l0aCBhIGNvcnJlY3QgcHJlZGljdGlvbiB0b3dhcmQgbmVnYXRpdmUuCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTCgiL3RtcC91Y2loZF9lYm1fZXhwX2ZwLmh0bWwiKQpgYGAKCiMgUmVmZXJlbmNlcwo=